2012 AIO(Intermediate) 赛题

2012 AIO(Intermediate) 赛题

NORT

Input File: nortin.txt
Output File: nortout.txt
Time Limit: 1 second

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.

Input

Your program should read from the file nortin.txt. The first and only line of this file will consist of two space-separated integers W and H respectively.

Output

Your program should write to the file nortout.txt. Your output file should consist of one line containing one integer: the length of the longest possible connected wall of light you can create.

Cabinet Shuffle

Input File: shufflein.txt
Output File: shuffleout.txt
Time Limit: 1 second

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 Anthem in 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.

Input

Your program should read from the file shufflein.txt.

• The first line of input will contain two space-separated integers N and K.
• The second line of input will contain K space-separated integers representing the points at which there are chairs, in increasing order. Hence, the first chair in this list will be the Prime Minister's.
• The third line of input will contain K+1 space-separated integers representing the points of ministers, in increasing order. The ministers are numbered from 1 to K+1 by their position in this list.

Output

Your program should write to the file shuffleout.txt. Your output file should contain two lines.

• The first line should contain one integer: the number of the minister who is in the first seat at the end of the game.
• The second line should contain one integer: the number of the minister who is left with no seat at the end of the game.

King Arthur II

Input File: arthin.txt
Output File: arthout.txt
Time Limit: 3 seconds

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.

Input

Your program should read from the file arthin.txt.

• The first line of input will contain N, the number of knights.
• The second line of input will contain P, the number of pairs of duel-prone knights.
• Each of the following P lines will contain two space-separated integers a and b, representing two knights who cannot be invited to the same meeting. It is guaranteed that a b and that the same pair will not appear twice in the input. Knights are labelled from 1 to N.

Output

Your program should write to the file arthout.txt. It should output a single integer: the maximum number of knights that can be invited to the first meeting without any chance of a duel occurring at either the first or second meeting.