![[BIO98 Logo]](../../../images/bio98-e-s.gif)
the computing competition for schools and colleges.
We are proud to present BIO'98.
![[Data Connection logo]](../../../images/dc_logo3-s.gif){kind=logo}
| |
The British Informatics
Olympiad is the computing competition for schools and colleges. We are proud to present BIO'98. |
|
 |
The 1998 British Informatics Olympiad exam
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 |
| 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:
|
| 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:
|
Sample run |
| 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 |
| 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