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.

Solution

想让比自己强的人比自己弱怎么办?拉到后面去

想让比自己弱的人比自己强怎么办?拉到前面去

位置不够怎么办?置顶!

The Troublesome Frog

Bazza and Shazza do not like bugs. They wish to clear out all the bugs on their garden fence. They come up with a brilliant idea: they buy some sugar frogs and release them near the fence, letting them eat up all the bugs.

The plan is a great success and the bug infestation is gone. But strangely, they now have a sugar frog infestation. Instead of getting rid of the frogs, Bazza and Shazza decide to set up an obstacle course and watch the frogs jump along it for their enjoyment.

\includegraphics[height=9em]{fence1}

The fence is a series of N fence posts of varying heights. Bazza and Shazza will select three fence posts to create the obstacle course, where themiddle post is strictly higher than the other two. The frogs are to jump up from the left post to the middle post, then jump down from the middle post to the right post. The three posts do not have to be next to each other as frogs can jump over other fence posts, regardless of the height of those other posts.

The difficulty of an obstacle course is the height of the first jump plus the height of the second jump. The height of a jump is equal to the difference in height between its two fence posts. Your task is to help Bazza and Shazza find the most difficult obstacle course for the frogs to jump.

Solution

维护一个前缀最小值和后缀最小值就可以了,时间复杂度O(n)

Save-It

The United Bakers of Australia (UBA) is once again in hot water. Profits have been crumbling recently due to a new tax on an invisible poisonous ingredient underpinning cake manufacturing. Rather than adapt their recipes to use healthier alternatives, the UBA has employed analysts from PwC (People with Cupcakes) to find a way to cut costs.

Upon inspection of UBA's purchasing practices, the analysts found that when a group of ingredients is ordered, the cost of the group is rounded to the nearest 5 cents. That is, a group's cost is the multiple of 5 that has the smallest difference with the sum of its ingredient costs.

For instance, two items costing 32c and 47c can be bought in separate groups for 30c and 45c, or 75c in total, whereas purchasing them in one group together would cost 80c (rounded up from 79c).

Your task is to put the required ingredients into groups for purchasing in order to minimise their total cost.

Solution

我一开始是想模10做,但是考虑到具体细节太麻烦,参考了晴川兄的做法后,发现模5就可以了

模5以后我们只需要考虑3~4,而[3,4]显然是一种比[4,4]优的方法,那么就先每个都拿一个,假如3剩余,就不断地组[3,3],假如4剩余,就不断地组[4,4,4]

这样就可以做到O(n)的效率

Art Class

You are attending a highly exclusive seminar run by the famous artist known only as Leo.

Leo is said to be highly influential in the art world. In fact, he invented all the genres of art. All of them. Impressionism, post-modernism, and even cave paintings. In this seminar, Leo teaches you about his newest style of art, which he calls post-cubist squarism.

A post-cubist squarist artwork is painted on a rectangular grid, in which each grid cell is either coloured or blank. Two adjacent coloured cells (vertically or horizontally, not diagonally) are connected, and a shape is a group of coloured cells that are directly or indirectly connected to each other.

The diameter of a shape is the greatest distance between any two of its cells.

The distance between two cells is the minimal number of up, down, left or right steps through the grid to get from one to the other. It doesn't matter whether the steps go through blank cells or even part of an entirely different shape.

In a stroke of genius, Leo realised that the most important aspect of a post-cubist squarist painting is the largest diameter of any shape. He announces that there is a reward for whoever can determine this in his newest artwork. Of course, Leo's genius won't help you now. But what about his computer? While no one else is looking, you steal his laptop and begin to code.

Solution

首先利用BFS灌水法弄出每个连通块,扣出来单独处理

我们现在就等于要求平面最大欧几里得距离,切比雪夫距离搞搞就行了

所谓切比雪夫距离,就是对于|x_{i}-x_{j}|+|y_{i}-y_{j}|拆分,容易发现四种情况的符号均相同,所以我们可以记录状态来进行枚举,时间复杂度O(n2^{dem}dem)

 

AIO2013 Solution(Chinese)》上有1条评论

  1. Pingback引用通告: 填坑计划一览表 | 一个沙茶的代码库

发表评论