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.

Solution

小学生题,每k+1个一循环,然后多余的算新的一次


Choreography

You are the long-suffering director of finance for the Australasian Academy of Aesthetic Arts, Astounding Acts of Acrobatics and Algebra. Week in, week out, the Academy organises increasingly elaborate and expensive arts events while you struggle to scrape together enough money to make ends meet.

The big thing this month is Machinations Infernal, a modern dance routine involving D dancers and H hula hoops. Each dancer is assigned a unique number between 1 and D, and starts off holding some number of hula hoops (possibly none). The dance routine is performed as a sequence of T throws where each throw is of the form "dancer i throws a hula hoop to dancer j" (where i and j represent different dancers). Each throw is performed in the order specified, one after another. No hoops may be thrown unless it is part of the routine.

For a dancer to throw a hula hoop, they clearly must hold at least one hoop at that instant. You have been tasked with determining how many hula hoops are needed at the start of the dance such that every dancer has one to throw when required by the routine. As everyone knows, hula hoops are very expensive, so you must determine the minimum number of hula hoops required for the dance routine.

For example, consider the following dance routine consisting of five dancers and eight throws.

1 → 3
2 → 3
2 → 1
5 → 2
3 → 5
1 → 4
3 → 4
4 → 5

One way to begin the routine is to give one hoop to dancer 1, two hoops to dancer 2, and one hoop to dancer 5. Dancers 3 and 4 begin with no hoops. The following table shows how many hoops each dancer has after each step of the dance.

Dancer
1 2 3 4 5
Initial set-up 1 2 0 0 1
1 → 3 0 2 1 0 1
2 → 3 0 1 2 0 1
2 → 1 1 0 2 0 1
5 → 2 1 1 2 0 0
3 → 5 1 1 1 0 1
1 → 4 0 1 1 1 1
3 → 4 0 1 0 2 1
4 → 5 0 1 0 1 2

With these four hoops, every dancer always has a hoop to throw when required and this in fact uses the fewest number of hoops possible.

Solution

一开始想二分,走远了。。。wa了好久

发现我忘记减度数了

事实上这就是个傻逼级别的贪心= =

怎么贪呢,就是模拟,当前的环不够就给他一个环,显然这样最优


Oil Spill

The enormous family-friendly multinational corporation PB (Pollution Busters) has been hitting headlines this year due to the 2010 Golf of Tigerius oil spill. After an oil rig explosion in April, the company has been in serious hot water.

Due to petroleum toxicity and oxygen depletion, the spill is an environmental catastrophe. It has damaged the local fishing industry, the tourism industry and the habitats of hundreds of wildlife species. PB however, is not particularly worried, as made clear in the CEO's statement that the oil spill is "relatively tiny" in comparison with the "very big ocean".

PB has refused to allow independent scientists to perform accurate measurements on the oil spill rate. The media has been prevented from viewing affected areas or flying over the spill, and threatened with arrest when attempting to investigate.

The international environmentalist organisation Green Peas has employed you to write a program to help them calculate the severity of the environmental impact.

Green Peas has given you a grid of R rows and C columns, representing the environment surrounding the oil rig. The spill originated at the rig, which will be marked on your map with a $'. Land squares will be marked with a #' and sea squares will be marked with a .'. Each day after the initial explosion, every sea square adjacent (north, east, south or west) to either the oil rig or a previously oil-covered sea square becomes covered by oil. Land squares are never covered by oil.

Your program must simulate the spread of the oil spill for K days, then output a map of the surrounding environment with oil-covered sea squares represented by *'.

Solution

灌水法裸题,记录下步长即可


Heatwave

Summer is fast approaching. There are people who love the sun, thrive in the warmth and enjoy lazing by the water. Then there are people who are irritated by the flies, the sand and of course the hot days. Different countries and cities tend to have different definitions of what is considered a "hot" day. For example, in Australia a hot day might be considered anything from 36 degrees up. However, in Iceland a day of 20 degrees or more is highly unusual and could send the locals into heat stress.

A "heatwave" is defined to be a series of one or more consecutive hot days. In hope of finding a nice warm city to retire, you wish to determine for a given city how many days the longest heatwave lasted. Your sources have obtained all the historical temperature data for the cities you are interested in, together with the lowest temperature that constitutes a heatwave for the city.

Your task is to write a program that can determine the longest observed heatwave.

For example, consider the following historical data for Perth. People in Perth call a day hot when the temperature hits 38 degrees or more. The hot days are underlined below:

31   39   42   33   30   33   40   38   39   41   37   34   27

Here, the longest heatwave lasted four days (the consecutive days where the temperature hit 40, 38, 39 and 41).

Solution

类似最大子段和一样扫一遍即可,时间复杂度O(n)


Snap Dragons

Have you ever heard of Melodramia, little one? It is a faraway kingdom: a land of daring knights and reclusive wizards, of terrifying gryphons and majestic phoenixes, of ice queens and talking lions. It is a place where every day is a fantastic adventure.

Once upon a time in Melodramia, there lived two dragons named Rose and Scarlet. They were the best of friends, never stealing each other's gold or kidnapped princes, and whenever they had an argument they always settled it with a game of Dragon Snap. Dragon Snap was a game they had invented, and it worked like this:

  • Rose would take R blank cards and write a secret number on each one. These numbers were in no particular order, and sometimes she would write the same number more than once.
  • Scarlet would take S blank cards and do the same.
  • At the same time, both dragons flipped over one of their cards at random. If these had the same number written on them, the cards were aSnap pair, and whichever dragon shouted "Snap!" first was the winner. Otherwise, they flipped the cards back over and tried again.

After many years of playing, the dragons noticed that having more possible Snap pairs would often lead to a faster game. For example, if Rose chose 6,4,2,4 as her cards and Scarlet chose 9,5,2 as her cards, then only 1 out of the 12 possible pairs would be a Snap pair (Rose's 2 paired with Scarlet's 2), and the game could go many rounds without finishing.

On the other hand, if Rose chose 8,9,9,9,9 as her cards and Scarlet chose 9,9,8,9,9,9 as her cards, then 21 out of the 30 possible pairs would be Snap pairs (1 pair of 8s and 20 pairs of 9s), and the game would end very quickly.

Curious, Rose and Scarlet called upon a powerful magician (i.e. you) to write a program that would read in the list of cards they had each chosen and calculate how many Snap pairs could be made.

Solution

开个桶,贡献计数法搞搞就行了


Hippopotamus Island

Somewhere in the middle of the Great Inspecific Ocean, there is a little-known island called Hippopotamus Island. This peculiar island is in the shape of a square with a side length of L kilometres. There are houses at one kilometre intervals all the way around the island, with the first house on the north-west corner, giving 4L houses on the island in total. Each house may contain some number of people (islanders) or it may be unoccupied. The centre of the island is inhabited by hippopotami who are easily frightened, and so the islanders only ever walk around the coast.

You wish to construct a desalination plant on the island to produce and sell fresh water. You will demolish one of the houses on the island and build the plant in its place. Your plan is to become the sole supplier of fresh water on the island so that every islander will need to travel to you in order to buy their water.

Your calculations say that for each kilometre that an islander must walk, they will buy one litre of water. For example, an islander who must walk four kilometres to get to the desalination plant will buy four litres of water. Note that the islanders can walk around the island either clockwise or counter-clockwise but they will always choose the shorter route to get to their water. If the desalination plant is built on a house containing islanders, you compensate their loss by offering them water for free.

Thinking deviously, you realise that you can sell more water by forcing islanders to walk further. The amount of water you sell is determined by the sum of the distances that each islander must walk to get to your plant.

 

Consider the above island of side length 3. There are 12 houses on the island, numbered in clockwise order starting from 1 in the north-west corner. Houses 2, 4, 11 and 12 contain 3, 1, 1 and 2 islanders, respectively. If for example, you were to place the desalination plant where house 4 is, you would sell nothing to the one islander you displaced, 3 x 2 = 6 litres to the islanders living in house 2, 2 x 4 = 8 litres to the islanders in house 12, and 1 x 5 = 5 litres to the islanders living in house 11, giving a total of 19 litres of water sold.

Alternately, if the plant was placed on house 8, you would sell 3  x  6 = 18 litres from house 2, 1  x  4 = 4 from house 4, 1  x  3 = 3 from house 11, and 2  x  4 = 8 from house 11, giving a total of 33 litres. This is the maximum amount of water that you can sell.

Your task is, given the size of the island and the locations of the islanders, write a program to determine the maximum amount of water you can sell by strategically locating your desalination plant on the island.

Solution

晴川司机太劲了啊QQ图片20160623113101

不妨记f(x)为将抽水泵建在x号房的答案

很容易发现,f(x)的图象是一条折线,不妨称折线的顶点为一个事件

是什么改变了这条折线的斜率了呢?无疑是有一个原本在x右边的变到了x左边

那么我们可以考虑增量法,先弄出折线的起始点(即0),然后顺序推每个时间,计算贡献即可

 

发表评论