[BIO99 Logo] The British Informatics Olympiad is
the computing competition for schools and colleges.
We are proud to present BIO'99.
[Data Connection logo]
-----

The 1999 British Informatics Olympiad - Sample paper

Time allowed: 3 hours

You should write a program for part (a) of each question, and produce written answers to the remaining parts. Programs may be used to help produce the answers to these written questions. You may use a calculator and the on-line help that your programming language provides.

Mark the first page used for your written answers with your name, age in years and school/college. Number all pages in order if you use more than one sheet. All of your computer programs should display your name and school/college when they are run, and the floppy disk you use to submit the programs should also show your name and school/college.

For your programs to be marked, the source code must be saved, along with executables if your language includes a compiler. This includes programs used to help answer written questions. You should also clearly indicate the name given to each program on your answer sheet(s).

Sample runs are given for parts 1(a), 2(a) and 3(a). Bold text indicates output from the program, and normal text shows data that has been entered. The output format of your programs should follow the 'sample run' examples. Your programs should take less than two minutes of processing time for each test.

Attempt as many questions as you can. Marks allocated to each part are shown in square brackets next to the questions. Partial solutions (such as programs that only satisfy some of the specified requirements, or partly completed written answers) may get partial marks. You may answer the questions in any order.

-----
Question 1
Roman Numerals
In Roman times, numbers were represented using letters. The way of doing this, known as Roman Numerals, is often seen depicting the copyright date on films and television.

Roman numerals are conventionally defined to represent numbers using seven letters: I=1, V=5, X=10, L=50, C=100, D=500 and M=1000. Numbers other than these are formed by placing letters together from left to right, in descending order of size, and adding their values. The basic rule is to always use the biggest numeral possible (e.g. 15 is represented as XV, but never as VVV, VX or XIIIII).

Letters may not appear more than three times in a row, so there are six exceptions to these rules - the combinations IV, IX, XL, XC, CD and CM. In these cases a letter is placed before one of greater value, and the smaller value is subtracted from the larger, e.g. CD = 400.

Examples:
26    XXVI
94    XCIV
555   DLV
1998  MCMXCVIII
1 (a)
[20 marks]
Write a program which accepts a number, between 1 and 3999 inclusive, and outputs the same number in Roman numerals.

Sample run
1999
MCMXCIX

1 (b)
[4 marks]
(i) What is LXIII + XXXVIII? Give your answer in Roman numerals.
(ii) What is MCCXLIX + DCXV? Give your answer in Roman numerals.
   
1 (c)
[6 marks]
Some Roman numerals have fewer characters than the number of digits in the number they represent, e.g. C (1 character) compared with 100 (3 digits). Similarly some have more characters (e.g. XXIV and 24), and some have the same length (e.g. V and 5). How many of the numbers from 1 to 3999 inclusive have fewer characters in their Roman numeral form, and how many have more?
-----
Question 2
Tamworth Two
A pair of pigs are loose somewhere in a large wooded area and an experienced farmer has been sent in to catch them. Your task in this question is to model their behaviour.

The chase takes place on a 10 by 10 grid, the bottom left square being (1,1). Squares can be empty or contain a tree, the pigs (who always travel together) or the farmer. Only the pigs and the farmer can ever share a square. Each square is represented as follows:

. Empty Square
* Tree
P Pigs
F Farmer
+ Pigs and Farmer

  The pigs wander around the grid in a set way. They move one square in the direction they are facing, unless there is a tree or the edge of the board in the way. If their move was blocked they just turn 90 degrees clockwise. The farmer, wise in the ways of pigs, moves in exactly the same way.

The farmer and the pigs can be considered to move simultaneously. If the farmer and the pigs pass each other during a move, they are not considered to have met. Furthermore, due to the difficulty in catching pigs, the farmer and pigs continue to move after they have met.

2 (a)
[24 marks]
Write a interactive program to model the behaviour of the pigs and farmer. Your program should first read in a line containing two numbers, the x co-ordinate then the y co-ordinate of the pigs. A second line should then be input, consisting of the co-ordinates for the farmer. Note that both the farmer and the pigs start by facing up the grid. You should then output the grid.

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

  1. If you receive the letter T followed by an integer n, you should read in n more lines, each consisting of the x and y co-ordinates for a tree. You should then display the grid. [Note: This does not count as a move.]
  2. If you receive an M followed by an integer n, you are to simulate the next n moves. If after any move during this simulation both the farmer and the pigs are in the same square, you should output how many moves have taken place (since the start of the program) and the square they have met at. After all n moves you should display the grid.
  3. If you receive an X, your program should terminate.
  4. Ignore any other input.

Sample run
5 6
4 8

..........
..........
...F......
..........
....P.....
..........
..........
..........
..........
..........


T 2
4 10
1 1

...*......
..........
...F......
..........
....P.....
..........
..........
..........
..........
*.........


M 4

Farmer and pigs meet
on move 3 at (5,9)

...*P.....
.....F....
..........
..........
..........
..........
..........
..........
..........
*.........


X

   
2 (b)
[2 marks]
Suppose the pigs start at (1,1), and they are trying to reach (10,10). What is the minimum number of trees that need to be placed on the grid to prevent the pigs reaching (10,10)? What is the maximum number that can be placed on the grid so that they can still reach (10,10)?
   
2 (c)
[3 marks]
Suppose you are able to place the farmer and the pigs on an empty grid, and you can choose the direction they are both facing (up, down, left or right). For a given starting position either they never meet, or they first meet after x moves. What is the maximum value that x can take?
   
2 (d)
[5 marks]
For a given grid, with trees and starting positions (with directions) for the farmer and pigs, will we always be able to determine whether or not the farmer and pigs will meet? Consider both the case where they will eventually meet, and when they will not.
-----
Question 3
Alphametics (Cryptarithms)
An alphametic is an arithmetic expression where the numbers have been replaced by letters. Each number is replaced by the same letter throughout the expression, and no letter is used to represent more than one number. Furthermore, the leftmost digit of any number is not allowed to be a zero. Given an alphametic, the problem is to reconstruct the original.
  The classic puzzle is SEND + MORE = MONEY. The only solution to this problem is
9567 + 1085 = 10652.

The restriction on the leftmost digit is important. It means, for example, that 8542 + 0915 = 09457 is not a valid solution.

3 (a)
[24 marks]
Write a program which solves addition alphametics. Your program should first accept a number n, between 3 and 6 inclusive, which will indicate the number of lines to follow. The following n lines will each contain a word of no more than 10 characters. The alphametic to be solved is the sum of the first n-1 words, to total the final word.

Sample run
3
SEND
MORE
MONEY
9567 + 1085 = 10652
Unique

  Your output should consist of an example solution if you believe there to be one, or the word 'Impossible' if you do not. If you find a solution and believe it to be the only one, you should additionally print out 'Unique'.  
   
3 (b)
[4 marks]
Find two solutions to BIO + ROUND = FIRST.
   
3 (c)
[3 marks]
If you are only allowed to use a single letter, is it possible to construct an addition alphametic with a solution? If you believe it is possible give an example alphametic, and if you believe it is impossible give a brief explanation why.
   
3 (d)
[5 marks]
An alphametic is being created, where ABC and DEA are to be summed, and the total is to only use the letters A, B, C, D or E. How many possibilities (i.e. valid letter combinations) are there for the total, so that the resulting alphametic has a solution? How many different sums can be represented by such an alphametic?

Total marks: 100.
End of BIO'98 Round One paper


The British Informatics Olympiad