In the book The Hunt for Red October by Tom Clancy, there is a moment in which the titular submarine's location is detected by a probe. A naval officer sees how that location starts off as a point but gradually becomes a circle with ever increasing radius as time proceeds and the location of the submarine therefore becomes ever more uncertain.
In this adversarial game, there is an admiral A and a submarine S. At every moment in time up to a time T, the admiral A will guess the position of S. If the guessed position is within distance D of the real position of S, then A gets one point for that moment in time. If the guessed position is strictly farther than D, then A loses five points for that moment in time. If A doesn't guess, then A loses one point for that moment in time.
The admiral is allowed to deploy at every moment in time one or more probes out of a total stock of k. Each probe may be deployed at any location and each will report back the information "the submarine is within radius R of my probe location".
The parameters k, R, T, and D will be given to you on the night of the competition. R will be strictly less than D.
The game is played on a 5D by 5D grid. The submarine can move one position vertically, horizontally, or diagonally at each time unit. If one or more probes is within a radius R, the submarine is told how many such probes there are.
Problem to warm up: If the submarine can move only on a line segment of length 100 and d is 20, what is the minimum number of probes that would be needed so that at every moment in time up to time 300 minutes from the starting time 0, the admiral would be able to identify a point that is within distance 20 of the submarine. Assume the submarine can move one unit in one minute. Could you do this with 65 probes or fewer?
Solution: Start by deploying probes at 20, 30, 40, 50, 60, and 70. This would be sufficient to know the probe within an interval of size 10. So for example could know that the submarine is within [0..9] if the probe at 20 detects the submarine but no other. The submarine is within [10..19] if the probes at 20 and 30 detect the submarine, but no others. The submarine is in [20..29] if the probes at 20, 30, and 40 detect the submarine, but no others. The submarine is in [30..39] if the probes at 20, 30, 40, and 50 detect the submarine, but no others. The submarine is in [40..49] if the probes at 30, 40, 50, and 60 detect the submarine (and possibly 20) but no higher ones. The submarine is in [50..60] if the probes at 40, 50, 60, and 70 detect the submarine (the probe at 30 may detect as well). The submarine is in [61..70] if the probes at 50, 60, and 70 detect the submarine. The submarine is in [71..80] if the probes at 60 and 70 detect the submarine. The submarine is in [81..90] if the probe at 70 detects the submarine. If no probes detect the submarine, then October is in [91..99]
At the end of the probing we know that the submarine is at some location [L..L+9]. We will make our point p be L+4 and know the submarine is within distance 5 of p.
Now we wait wait 15 time units at which point the submarine is in the interval [L-15..L+24]. Now we put probes at locations L-26, L+25, and L+35. The submarine is at [L-15..L-6] if only probe L-26 detects it. The submarine is at [L-5..L+4] if no probes detect it. The submarine is at [L+5..L+14] if L+25 detects it but L+35 does not. The submarine is at [L+15..L+24] if L+25 and L+35 both detect it. We can do this probing every 15 time so we would need 9 probes initially and then 3 probes every 15 time units. So we would need 6 + 19*3 = 63 probes. End of example.
Your job is to perform this probing on two dimensions.
Show the layout of the board and the position of the submarine, the positions of the probes when they are done, the guesses done by the admiral, the running score, and the current time. The architect must also receive position movement information from the submarine and of course probe and guess information from the admiral.