The British Informatics
Olympiad is the computing competition for schools and colleges. We are proud to present BIO'99. |
The 1999 British Informatics Olympiad - Round One
Question 2 Black Box (Atom) |
Scientists are studying an
enigmatic Black Box by firing rays into it and observing
the results. The rays are influenced by atoms within the
box. Your task for this question is to model the rays'
behaviour. The box is a 10 by 10 grid. Each square is either empty or contains a single atom. The 36 squares on the boundary of the box, i.e. the squares adjacent to an outside edge, never contain atoms. Rays are fired into the box from a point on the grid's edge, and can travel horizontally and vertically. Rays continue travelling in straight lines, unless affected by atoms as follows:
These rules are given in order of precedence. Note that sample ray 1 is absorbed rather than deflected. |
2 (a) [25 marks] |
Write an interactive program
to show how the rays are affected by a black box
containing five atoms. The entry and exit points for rays will be given by a single letter followed by an integer. The letter, 'T', 'B', 'L' or 'R', indicates the side of the grid: top, bottom, left or right. The number indicates the position on the given side; for the top and bottom sides, 1 is on the left; for the left and right sides, 1 is at the bottom. Your program should first read in 5 lines each containing two numbers; the x co-ordinate then the y co-ordinate for an atom. The bottom left corner is (1,1). You should then output the black box - using '.' for an empty square and 'A' for one containing an atom. Until your program terminates you should repeatedly wait for input, and then:
|
Sample run 3 3 9 3 3 5 5 9 6 9 .......... ....AA.... .......... .......... .......... ..A....... .......... ..A.....A. .......... .......... T 6 .....+.... ....A*.... .......... .......... .......... ..A....... .......... ..A.....A. .......... .......... Absorbed R 6 .......... ....AA.... ++++...... ...+...... ...+++++++ ..A....... .......... ..A.....A. .......... .......... Exits at L 8 L 4 .......... ....AA.... .......... .......... .......... ..A....... ++........ ..A.....A. .......... .......... Reflected T 8 .......+.. ....AA.+.. .......+.. .......+.. .......+.. ..A....+.. ...+++++.. ..A.....A. .......... .......... Reflected X 0 |
2 (b) [3 marks] |
What is the smallest number of atoms that can be placed in an empty black box, so that all 40 possible rays will be affected? Draw a suitable arrangement to illustrate your answer. |
2 (c) [4 marks] |
A ray is fired into a box at T 5 and emerges at B 5. If there are four atoms inside the box, how many different paths might that ray have taken? |
2 (d) [8 marks] |
A ray might pass through a square once (e.g. squares on the path of sample ray 2) or twice (e.g. squares on the path of sample ray 3). How about exactly 3 times? How about exactly 4 times? Justify your answers. |