[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 - Round One

Question 2
Black Box (Atom)

[See sample run]

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:

  1. If the ray hits an atom it is absorbed (example ray 1).

  2. If the ray is about to pass though a square next to an atom, it is deflected by 90 degrees away from the atom (example ray 2).

  3. A ray that would pass between two atoms one square apart is reflected (example ray 3).

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:

  1. If you receive 'T', 'B', 'L' or 'R' followed by an integer between 1 and 10, you should treat it as the entry point for a ray. You should display the black box, using a '+' to indicate any square the ray enters which was empty, and a '*' for any it enters that contained an atom.

    If the ray was absorbed or reflected you should output the corresponding word; otherwise you should output the exit point.

  2. If you receive the input "X 0" you should terminate.

  3. Ignore any other input.

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.

The British Informatics Olympiad