AIO2005 Solution

Cute Numbers

For you, numbers have personalities. The number 4 is elegant, 18 is strong and 42 is enigmatic. And, of course, any number ending in 0 is cute.

The more zeroes at the end of a number, the cuter that number is. Therefore 70, 36640 and 1800090 are only a little bit cute (ending in just one zero), whereas 400 and 99200 are very cute (ending in two zeroes) and 30000 is really really cute (ending in four zeroes).

Your task is to read in a number N and determine how many zeroes are at the end of that number, so you can tell just how cute the number is.

Solution

思博题,代码都不想贴


Curry

You are at a very fancy dinner party with some very good friends, trying to eat a very hot curry. On your plate is a pile of curry, rice and vegetables. You are finding it quite difficult to eat, since the curry is too hot, the rice is too sticky and you don't like vegetables.

To work around this problem, you eat in such a way that each mouthful includes a scoop of two different items. For example, the first mouthful might include a scoop of curry with a scoop of rice. The next mouthful might include a scoop of rice with a scoop of vegetables. You cannot eat three scoops all at once, since your spoon is too small.

The danger with your plan is that you might not be able to finish your meal. At last week's dinner party you started off by eating all your curry and rice, which meant that you could not finish your vegetables since there was nothing left to eat them with. It was most embarrassing. Determined not to be humiliated again, you pull your laptop out of your bag and tap away secretly beneath the table, hoping to solve your eating problems for once and for all.

Your task is to work out how to eat your meal so that you eat as much total food as possible.

Solution

每次取最大的两个减下就好了,懒得写if于是干脆用了优先队列


Landmark

You are mayor of the city, and it's almost election time. It is clear to you that the only way to get re-elected is to construct a huge landmark in the centre of the city. Perhaps a bird park, since the polls show that most people associate colourful birds with happiness.

Trouble is, the city is already full of buildings and there is no free space. To build your bird park, you will need to knock some buildings down.

The city is divided into square blocks. Each block is either commercial or residential. You cannot knock down any commercial buildings, since the businesses will get angry and stop donating to your campaign fund. You therefore need to find a suitable residential area that can be knocked down so that you can build your new bird park and make your citizens happier people.

The bird park will be rectangular in shape. Due to building regulations it may only be one block wide, though it can be as long as you like. The bird park may be placed either horizontally or vertically in the city.

Two city maps of 5 x 6 blocks are illustrated below. In each map the commercial blocks are coloured black, and the blocks used to create the largest possible bird park are marked with the letter B. In the first map, the largest possible bird park is horizontal and four blocks in length, whereas in the second map it is vertical and three blocks in length.

You must write a program that can read in a city map and find the location where you can build the largest bird park possible, thereby securing your re-election.

Solution

一开始以为是最大全0子矩阵于是乎写了一发悬线法。。扫了一眼题意发现这玩意宽度为126

然后暴力搞搞就好了


Sculpture

As a highly acclaimed sculpture artist, you have been commissioned to make an abstract 3-dimensional artwork to commemorate the Melbourne International Fruit Festival.

You have decided to construct an elaborate tree by joining apples together with sticks of wood. The artwork will have a single apple at its base, with two wooden sticks rising up to meet new apples. Each of these apples has two more wooden sticks rising up to meet two new apples, and so on. An example of such a tree is illustrated below, where the apples are numbered from 1 to 9 and the lengths of the sticks are shown.

Note that some apples have two new sticks rising up, and others have none. You never have only one stick rising up, since this upsets the delicate artistic balance of the work.

Consider the apples with no new sticks rising up — call these the top apples. In the example above, the top apples are numbers 4, 5, 7, 8 and 9. By examining the stick lengths, we can measure the distance from each top apple to the base of the tree. These distances are as follows.

The Director of the festival has passed by to inspect your artwork. She likes the idea, but is unhappy that the top apples look so messy. You are therefore instructed to lengthen some of the wooden sticks so that all the top apples are precisely the same distance from the base.

Unfortunately you are running short of wood, and so you would like to add the smallest total length possible. For the example above, you could change the stick lengths as follows (changed lengths are indicated with arrows).

Here you have increased the sticks by a total length of 1+3+2 = 6 (which is the smallest total increase possible). The distances from the top apples to the base are now as follows.

Since these distances are all the same, the Director is happy and you can exhibit your artwork to receive the fame and glory that such a piece deserves.

You must write a program that reads in a tree of apples and sticks, and then determines the smallest total increase in stick lengths that is needed to bring all top apples to the same distance from the base.

Solution

考虑贪心,显然尽可能往离根近的边加值最优,但是加值要考虑到不能溢出上限

那么问题来了,上限怎么确定呢?(上限即调整后最终根到叶子节点的距离)

结论是,一开始根到叶子节点的距离的最大值即为上限,大概yy下就能发现是正确的

于是大概做法是:

先跑一次树DP,记录以i为根的最远节点到整棵树的根的距离的最大值

那么我们的上限就是dp[1]

再进行一次分治即可,时间复杂度O(n)


Chimpanzee

It has been a long hard day trekking through the jungle, and it is almost dark. Exhausted, you sit down to rest and pull a book from your backpack for some light reading. Suddenly, with an excited cry, a chimpanzee leaps from a nearby tree and snatches the book from your hands.

In horror you watch as the chimpanzee runs through the jungle in a spiral pattern, ripping pages from your book as it goes. Soon your horror gives way to curiosity as you contemplate the very precise spiral pattern that the chimpanzee is following.

Consider the jungle to be a grid of squares in a coordinate system, where you are sitting at square (0,0). The chimpanzee follows a tight spiral out from (0,0) as illustrated below.

The pages of your book are numbered from 0 upwards. At each square on the spiral, the chimpanzee tears a new page from your book. Thus page 0 is left at square (0,0), page 1 is at square (1,0), page 2 is at square (1,1), page 3 is at square (0,1), page 4 is at square (-1,1) and so on.

Fortunately you have also brought your laptop on your jungle trek. Pulling it from your bag and plugging it into a nearby power point, you sit down to write a program that will help you put the pages together in the correct order.

Your specific task is to write a program that reads in a pair of (x,y) coordinates and outputs which page the chimpanzee has left in that square.

Soluion

Assert把数据崩出来了2333,然后不断修改终于成功了QQ图片20160623113147

大概就是分象限,举例子,然后手推推,然后assert崩出数据判断哪里错了

 

发表评论