The 2005 British Informatics Olympiad - Sample paper

The Mayan civilisation used three different calendars. In their long count calendar there were 20 days (called kins) in a uinal, 18 uinals in a tun, 20 tuns in a katun and 20 katuns in a baktun. In our calendar, we specify a date by giving the day, then month, and finally the year. The Maya specified dates in reverse, giving the baktun (1-20), then katun (1-20), then tun (1-20), then uinal (1-18) and finally the kin (1-20).

The Mayan date 13 20 7 16 3 corresponds to the date 1 January 2000 (which was a Saturday).

Write a program which, given a Mayan date (between 13 20 7 16 3 and 14 1 15 12 3 inclusive), outputs the corresponding date in our calendar. You should output the month as a number.

You are reminded that, in our calendar, the number of days in each month is:

In the game of Four in a Line, two players alternate dropping pieces of their own colour into a vertical board. The board consists of seven columns, each of which can hold six pieces. On their turn, a player can choose to drop their piece into any column which still has an empty space. When a piece is dropped into a column, it falls to the lowest unused position in that column.

The winner is the first player to form a line of four adjacent pieces of their own colour; horizontally, vertically or diagonally.

A simple strategy is for a player to choose their moves based on the following rules:

1. If there is a move which will win the game immediately, this move is played. If several such moves exist, the leftmost one is played.
2. If rule 1 does not indicate which move to take and there is a move which, if played by the other player would cause them to win immediately, this move is played. If several such moves exist, the leftmost one is played.
3. If neither rule 1 nor rule 2 indicates which move to take, play in the leftmost column which still has empty space.

The following examples demonstrate the simple strategy on some typical boards. Note that the boards themselves have arisen from an initial sequence of moves that did not follow the strategy.

The first player's pieces are shown using and the second player's pieces are shown using . The columns are numbered from left to right, with the leftmost column being number 1.

If it is the first player's turn on the following board, they must play in column 3, according to rule 1, to win with a horizontal line of four pieces.

Write a program to play Four in a Line. Both players will be controlled by the computer and play using the simple strategy.

Your program should first read in a single integer, n (1≤n≤10). This will be followed by a line containing n integers, indicating the columns for the first few moves of the game; the first number indicating the first move for player one, the next number indicating the first move for player two, etc. The columns are numbered from left to right, with the leftmost column being number 1. None of these initial moves will generate a winning line.

You should then output the board, indicating empty spaces with a -, pieces belonging to player 1 with a * and pieces belonging to player 2 with an o.

Until your program terminates you should repeatedly wait for input, and then:

• If you receive the letter n, you should play the next move of the game.
• If you receive the letter r, you should play the rest of the game, until one player has won or the board is full.
• Ignore any other input

After each command, you should output the board. If the game has been won you should output Player 1 wins (for a first player win) or Player 2 wins (for a second player win), and then terminate. If the board is full, you should output Draw and then terminate.

[In the sample run, the comments shown in italics in square brackets are for information only. These should not be entered into, or produced by, your program.]

The BIO has been receiving telegrams congratulating it on reaching its 10th anniversary. At least, we think it has. The telegrams have been sent in Morse code and, unfortunately, the gaps between letters have been left out.

In Morse code, each letter of the alphabet is replaced by a sequence of dots and dashes as follows:

Every combination of between 1 and 4 dots and dashes is used, except for:

..--
.-.-
---.
----

Traditionally, dots were transmitted by a short note and dashes by a longer note, with pauses between different letters. This is why some mobile phones make the sound ... -- ... when receiving a message, since this is the Morse code for SMS.

If the gaps between letters are missed out, messages can be ambiguous. For example, even if we know the message
-..-----. is made up of three letters, it might mean njg, dog, xmg or xon.

It is possible to come up with new ways of encoding the alphabet so that, even when the gaps between letters are missing, messages are unambiguous. The size of such an unambiguous encoding is the total number of dots and dashes in a message containing each letter once.

For example, we could encode each letter by some dots (indicating its position in the alphabet) followed by a dash; so .- would be a, ..- would be b, and 26 dots followed by a dash would be z. This encoding has a size of 377 (2 + 3 + ... + 27).

What is the smallest size an unambiguous encoding can have?