![[BIO97 Logo]](../../../images/flag97s.gif)
Sponsored by Data Connection.
![[Data Connection logo]](../../../images/dc_logo3.gif){kind=logo}
| |
The British
Informatics Olympiad Sponsored by Data Connection. |
|
 |
| Sample Paper |
This sample paper is taken directly from the 1996 British Informatics Olympiad and shows the type of questions which will be set in this year's competition. This paper has the same format as the 1997 BIO round one paper: 3 programming tasks in order of increasing difficulty, supplemented by written problems, with a time limit of 3 hours.
| |
For each question you are required to write a program for part (a), and produce written answers to the remaining parts. Programs may be used to help produce the answers to these written questions, and you may use a calculator. Marks for each part are given in square brackets by the questions. An example run is given for parts 1(a), 2(a) and 3(a). Bold text indicates output/prompts from the program, and normal text shows data that has been entered. The output format of your programs should follow the 'example run' examples.
|
| Question 1 [Solution] |
Two numbers are said to be 'amicable' if they are
different and the sum of the divisors of each number
(including 1 but excluding the number itself) equals the
other number. For example: 2620 is divisible by 1, 2, 4, 5, 10, 20, 131, 262, 524, 655 and 1310; these add up to 2924. 2924 is divisible by 1, 2, 4, 17, 34, 43, 68, 86, 172, 731 and 1462; these add up to 2620. Therefore 2620 and 2924 are amicable. |
||
| 1 (a) [20 marks] |
Write a program which inputs two numbers (which will be less than 10,000) and then prints "Amicable" if they are amicable, or "Not amicable" otherwise. Your program should then terminate. | Sample
run First number: 2620 Second number: 2924 Amicable |
|
| 1 (b) [3 marks] |
Which is the lowest pair of amicable numbers? | ||
| |
| Question 2 [Solution] |
'Life' is a
computer simulation played out on a rectangular board of
squares. Each square has two possible states, on ('0' -
zero) or off ('.'), and the state of the squares at the
next generation is fully determined by the current state
and some simple rules. The configuration at generation 0
is selected by the user. Each square on the board has eight neighbours, those touching it directly (including diagonally), except border squares which have some of these pieces missing. The rules for generating the next generation are: |
| Survival | Any 'on' square with two or three neighbouring 'on' squares stays 'on' next generation. |
| Death | Any 'on' square with less than two or more than three neighbouring 'on' squares goes 'off' next generation. |
| Birth | Any 'off' square with exactly three neighbouring 'on' squares goes 'on' next generation. Otherwise it stays 'off'. |
| The rules stay the same for border squares, though they have fewer neighbours - in other words squares outside the 11x11 board are to be treated as permanently off. You should also remember that all births, deaths and survivals between generations occur simultaneously. For example: |
| Generation 0 | ..0.. ...0. .000. ..... ..... |
Generation 1 | ..... .0.0. ..00. ..0.. ..... |
Generation 2 | ..... ...0. .0.0. ..00. ..... |
| 2 (a) [25 marks] |
You are to
write a program to play Life on an 11x11 board. Your
program should first read in a 5x5 board, which will be
in the form of five lines of five characters (either '0'
or '.'). This 5x5 board should be used as the centre
section of the 11x11 board for generation 0, the rest of
which is to be treated as off. This will be generation 0
for the entire run of your program. Once this is done you
should display generation 0. Until your program terminates you should repeatedly wait for input, and then:
|
Sample
run ..... ..... ...0. ....0 ..000 ........... ........... ........... ........... ........... ......0.... .......0... .....000... ........... ........... ........... #5 ........... ........... ........... ........... ........... ........... ........... ......0.0.. .......00.. .......0... ........... +1 ........... ........... ........... ........... ........... ........... ........... ........0.. ......0.0.. .......00.. ........... -1 |
|
| 2 (b) [4 marks] |
Why is it not feasible to have a '-n' option, which would calculate 'n' generations earlier? |
| 2 (c) [3 marks] |
A 'rule set' for Life is the collection of Survive, Death, and Birth rules. Another rule set, for example, could have the same Survive and Death rules, but allow Birth with 3 or 4 adjacent 'on' squares. Note Survive, Death and Birth rules can only depend on the number of adjacent 'on' or 'off' squares. How many possible rule sets are there? |
| 2 (d) [8 marks] |
Suppose we now limit rule sets so that the only valid Birth rules require "exactly 'n' neighbouring 'on' squares". Consider when generation 0 consists of the middle 5x5 squares all 'on', and all the other squares 'off'. How many rule sets produce, at generation 5, an 11x11 board with all squares 'off'? |
| |
| Question 3 [Solution] |
A domino is a 2x1 rectangle with 0, 1, 2, 3, 4, 5 or 6 written on each 1x1 half. A set of dominoes consists of the 28 unique dominoes. A domino with the same number on both halves is called a 'double'. | ||
| 3 (a) [25 marks] |
You are to
write a program that will fit a set of dominoes onto a
grid which is 7 squares high, and eight squares across.
This is to be subject to restrictions, in the form of
doubles in fixed positions, and to the rule that two
touching squares can only be equal if they belong to the
same domino. A square should only be considered to touch
the four squares directly above, below, left or right.
Dominoes may not overlap. You should first read in input indicating where the fixed doubles are. For each double this will be in the form of an x co-ordinate and y co-ordinate for one of the halves of the domino, and a R or B to indicate whether the other half is to the right or below. The top left corner of the board is at (1,1). The list of doubles will terminate with the number -1. Note that not all the doubles may be fixed, and that their value is left for you to decide. Once you have read the list you should try and fit the other dominoes to the grid. You should then output a valid solution if there is one, or print 'Impossible'. Your program should then terminate. |
Sample
run8 3 B
4 1 R
5 7 R
-1
0-1 0 1-1 0-3 0
| |
5-0 2 0-6 1-2 4
1-3 1-4 1-5 1 0
| |
3-2 4-2 5-2 6 0
2-6 3-4 3-5 3-6
4-5 4-6 5-6 5-5
6-6 3-3 2-2 4-4 |
|
| 3 (b) [4 marks] |
Suppose you are given some double restrictions, and a valid solution to the problem. Can you guarantee (or not) that there are any other solutions? | ||
| 3 (c) [8 marks] |
Without any restrictions on doubles or the values on touching dominoes, how many ways can 28 dominoes be placed on the 7x8 board? | ||
| |