分类目录归档:灌水法

AIO2010 Solution

Ninjas

You used to like ninjas. That was before the shadowy shiro-obi ninja clan moved in next door. They're mostly decent neighbours - they keep to themselves and never throw loud parties - but every few nights they sneak into your house and raid the kitchen. With no one else to turn to, you decide to take matters into your own hands and catch them in the act.

There are N ninjas trying to get inside, one at a time. You wait and watch carefully, grabbing the first one who comes past. However, in the time it takes you to securely tie up this first ninja, K other ninjas manage to sneak past you. Nevertheless, you persevere, grabbing the next ninja. Again, while you tie them up, K more ninjas sneak past. This continues until all of the ninjas have tried to get in.

\includegraphics[width=15cm]{ninjaexample}

In the above example, K=2. That is, for each ninja you tie up, the following two ninjas will sneak past. You catch the first ninja who comes past, and then ninjas #2 and #3 sneak past you. You catch ninja #4, and then ninjas #5 and #6 sneak past you. This repeats until all N ninjas have either been caught or have snuck past you.

Your task is to write a program that reads in the values of N and K, and calculates the number of ninjas who sneak past you.

继续阅读

AIO2013 Solution(Chinese)

Archery

When you were young, you were awe-struck by the battle scene in The Lord of the Rings: The Two Towers. From then on, you were determined to become the greatest archer of all time. After years of training, you are finally at the International Archery Olympiad (IAO), in Auckland.

On each of the two days of the IAO, all contestants are given a score and ranked by that score. After the second day of competition, all contestants are given an overall score equal to the sum of their two scores and their overall rank is then calculated from this.

Katniss Legolas Link Merida Robin
Day 1 Score 50 70 20 40 0
Day 1 Rank 2 1 4 3 5
Day 2 Score 30 20 40 50 40
Day 2 Rank 4 5 2 1 2
Overall Score 80 90 60 90 40
Overall Rank 3 1 4 1 5

A contestant's rank is equal to the number of competitors with strictly greater scores than theirs, plus one. In the above example, there are two overall scores strictly greater than Katniss's, so her overall rank is (2+1)=3. There are no overall scores strictly greater than Legolas's, so his overall rank is (0+1)=1. (Notice that Legolas and Merida are both ranked 1, as no one has a strictly greater score than either of them.)

Sick with anticipation of the results, you sneak a look at a judge's laptop. The scores aren't shown, nor is your overall rank, but you do manage to glimpse your first-day rank and your second-day rank. You want to work out what your overall rank could be.

Your task is to write a program which, given the number of contestants in the IAO and your rank on each day, determines your best and worst possible overall rank.

继续阅读

[bzoj 1102][POI2007]山峰和山谷Grz

Description

  FGD小朋友特别喜欢爬山,在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排,他想
知道山峰和山谷的数量。给定一个地图,为FGD想要旅行的区域,地图被分为n*n的网格,每个格子(i,j) 的高度w(
i,j)是给定的。若两个格子有公共顶点,那么他们就是相邻的格子。(所以与(i,j)相邻的格子有(i?1, j?1),(i?1
,j),(i?1,j+1),(i,j?1),(i,j+1),(i+1,j?1),(i+1,j),(i+1,j+1))。我们定义一个格子的集合S为山峰(山谷)当
且仅当:1.S的所有格子都有相同的高度。2.S的所有格子都联通3.对于s属于S,与s相邻的s’不属于S。都有ws >
ws’(山峰),或者ws < ws’(山谷)。你的任务是,对于给定的地图,求出山峰和山谷的数量,如果所有格子
都有相同的高度,那么整个地图即是山峰,又是山谷。

继续阅读