AIO2012 Solution(Chinese)

NORT

It is the year 1982. Malcolm Fraser is the Prime Minister of Australia, you frequently listen to Down Under by Men at Work on your boombox and roller blading is the default mode of transport. As a budding computer scientist, you spend most weekends at the local arcade trying to top your score in the popular video game NORT.

NORT is played on a rectangular grid of square cells with H columns and W rows. You ride a light-bike through the grid, starting in the top-left corner cell. Each second, you can move your light-bike up, down, left or right to any of the four adjacent grid cells (as long as you don't go off the grid!). As you move, your bike's exhaust pipe creates an impenetrable wall of light in the cell you were previously in. If you ever move into a cell containing a wall of light (i.e. a cell you have travelled through before), your bike will disintegrate into pixels in a dramatic 8-bit explosion. The only exception is if you return to the top-left corner cell where you started, in which case the wall of light will be connected and your score for the game will be the total length of wall you have created.

Your goal is therefore to plan the longest possible route through the grid starting and ending in the top-left cell without ever passing through a cell more than once.

Solution

贪吃蛇玩过对吧。。然后就没了

好吧正经题解:当且仅当n,m均为奇数时答案为n\times m-1,否则答案为n\times m

至于证明。。就是类似贪吃蛇那样的先走上、右外围,然后下来,然后一圈一圈绕,这显然是最优方案,公式手推下?。。。


Posters

You run a poster advertisement company. Your company is quite small: all it owns is a rectangular wall in the city. Advertisers pay to put up their poster on your wall at some time at some position along the wall. These posters may have different widths, but are all exactly the same height as the wall. When a poster is put up, it may cover some of the posters already on the wall.

You have a log of every single poster put on your wall: their distance from the left end, their width, and the time they were put up.

Since people always walk from the left to the right of your wall, and we all know advertisement posters are only effective when they are completely uncovered (e.g. a burger picture will only be mouthwatering if you see the whole burger), you would like to determine the leftmost fully visible poster

Solution

没想出比O(n\log n)优的方法...直接拿暴力走人算了QQ图片20160623113147

先对左右端点进行离散化,离线处理数据,每次更新一段,然后检查一段是否为0,为0则记录答案

时间复杂度O(n\log n)


Cabinet Shuffle

The polls are looking grim for the government of Absurdistan. Leadership speculation and high-profile scandals dominate popular current affairs shows Tomorrow This Morning and An Antiquated Event. In order to radically change public perceptions, the leaders plan to remove a ministry position and blame all the problems of the day on the ousted minister. At the same time, the other cabinet positions will be shuffled so as to portray a fresh, new face of government.

Naturally, the ministers can not agree between themselves who will be blamed and expelled, nor can they agree who will take which remaining ministry positions (including the position of Prime Minister). They decide to play a fair game of Musical Chairs to the tune of Party Rock Anthemin order to resolve these disputes.

There are K ministry positions available, each represented by a physical seat at a point around a circle. The K+1 ministers are also initially standing at points around the circle. Points on the circle are labelled clockwise from 1 to N, such that point 1 immediately follows point N. No two ministers will be initially standing at the same point, and no two chairs will be at the same point.

Each second, all the ministers who are still standing do the following (simultaneously):

  • If the minister is standing at the same point as an empty chair, the minister will sit down in it.
  • Otherwise, the minister will step one place clockwise around the circle to the next point. If the minister was previously at point i (with i < N), the minister will now be at point i+1. If the minister was previously at point N, the minister will now be at point 1.

Since there are K+1 ministers, eventually all K seats will be taken and the one minister remaining without a seat will be booted out and shamed by the media. Furthermore, the minister sitting in the first seat in the circle will have the place of Prime Minister. (The 'first' seat in the circle is defined as the first seat clockwise from point 1.)

Your task is to determine who will be Prime Minister and who will be expelled from cabinet after the reshuffle. Note that your program can score half of the available marks for correctly answering only one of these questions, and will score full marks for correctly answering both.

Solution

晴川巨巨太神了啊QQ图片20160623113101

我愣是没看出这是个环形括号匹配。。。

环形咋做呢?先直接跑一遍,发现剩下来的一定会是形如))))(((((这种情况

而显然是两头匹配,这样再做一次,就可以了

时间复杂度O(n)


King Arthur II

It has been many years since King Arthur has held a meeting for the Knights of the Round Table. Despite his best efforts to arrange seating in order to minimise conflict between knights, the last meeting deteriorated into a chaos of insulting and duelling unfit for the honourable dining room of Camelot.

Arthur must bring his knights together again, for rumour has spread throughout the kingdom that the dragons are becoming restless. In order to avoid the disasters of the last meeting, Arthur has decided to hold two meetings instead of one, and ensure that no two knights who would likely duel each other are invited to the same meeting. Furthermore, since immediate anti-dragon action is required, Arthur would like to have as many knights as possible at the first meeting.

After making a long list of all the knights and all the pairs of knights who may duel if invited to the same meeting, Arthur has requested you as the Court Informatician to write a program determining the largest number of knights that can be invited to the first meeting such that no pair of knights likely to duel each other are invited to the same meeting. Merlin, in his infinite wisdom, has assured you that there is at least one way of dividing all the knights into two meetings without any chance of duelling at either meeting.

Solution

由于保证了一定有解,那么每个子图一定是一个二分图,我们只需要进行黑白染色,取出每个子图的白色、黑色中较大者进行累加即可,时间复杂度O(n+m)


Awesome Frog

The inaugural International Olympiad in Frogleaping is being held in Australia in 2013 and you are determined to win. While you want nothing to do with such slimy, jumpy creatures, you plan to enter a frog-like robot that you know will be faster than all the other organic entrants.

The IOF takes place in a large pond in which there is a sequence of lily pads arranged in a long line. The rules of the race are simple: your frog will be placed on the first lily pad, then it must jump to the second lily pad, then the third and so forth until it reaches the last lily pad in the course. Note that you can not `skip' lily pads--every lily pad must be jumped on exactly once. The first frog to reach the last lily pad will win the race. Since your robotic frog has super-frog speed, you are confident in your victory.

However, your frog has one minor incorrectable flaw--it is only able to jump one fixed distance. Specifically, it can only jump exactly K metres forward from its current location, even if this lands the frog in the water (where it will promptly short-circuit).

Since the initial lily pad positions may make it impossible for your frog to reach the last lily pad, you plan to create a distraction and move the lily pads so that they are spaced exactly K metres apart, enabling your frog to jump from the first to the last without falling in the water. Shifting a lily pad by one metre will take you one second, and the longer you spend stealthily moving lily pads, the more likely that the IOF judges will notice and disqualify you from the competition.

Given the initial distances between the lily pads in the course, you must write a program to compute the minimum time you will have to spend shifting lily pads such that all pairs of consecutive lily pads are exactly K metres apart. You can assume that the pond is sufficiently long so that the first lily pad can be moved any distance back, and the last lily pad can be moved any distance forward.

Solution

和均分纸牌比较像,设花费函数为f(x),总花费为w,第一块石头的最优坐标为x

f(i)=|x-(a[i]-i\times k)|,w=\sum_{i=0}^{n-1}f(i)

然后画个图像大概就知道当x取值为a[i]-i\times k的中位数时,w最小

时间复杂度O(n)

 

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

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

发表评论