Hide

Problem F
Hunt the Wumpus

Hunt the Wumpus is a game you play against the computer on a $10 \times 10$ grid. At the beginning of the game, four wumpuses are randomly placed on the grid (with no two sharing a location). You need to find and capture all four wumpuses. You guess a square by entering the coordinates as two decimal digits. If you correctly guess the location of a wumpus, you are told you did so, and that wumpus is captured and removed from the grid. Whether or not you hit a wumpus, the Manhattan distance between your guess and the closest wumpus is reported to you. You can use this to locate and find each wumpus. The game ends when the last wumpus is captured.

You have been asked to write the computer portion of the game. User guesses and randomly-generated wumpus locations are defined by a two-digit number, where the high digit is $x$ and the low digit is $y$ for the point $(x, y)$.

To make the game deterministic, we will use our own pseudo-random-number generator, with a supplied seed $s$. Each random number is generated by first setting $s \leftarrow s + \hbox{floor}(s/13) + 15$ and then returning the two low digits of $s$. The first four distinct numbers generated by this process are the locations of the four wumpuses. For a seed of 132, the first location is given by the two low digits of $132 + 10 + 15$, which is $57$ and corresponds to the position $(5, 7)$.

Input

The first line contains a single integer $s$ ($10^4 \le s\le 10^6$), the seed for the random number generator. Each of the remaining lines contains a two-digit number (possibly with leading zeros). These are the guesses that a player has made, each corresponding to a single grid location.

The input will always be well-formed, and will describe a complete game. The last user guess will always find the last wumpus. There will be at most 250 guesses in any input.

Output

Output the computer’s response for each player guess. If a guess hits a wumpus, you should output “You hit a wumpus!” on a line. Whether or not the player hit a wumpus, if any wumpuses remain uncaptured, output the Manhattan distance to the closest remaining wumpus. The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$, and will therefore always be an integer.

At the end of the game, report the total number of moves $m$ required to locate all the wumpuses by outputting “Your score is $m$ moves.” on a line.

Sample Input 1 Sample Output 1
203811
00
01
02
03
You hit a wumpus!
1
You hit a wumpus!
1
You hit a wumpus!
1
You hit a wumpus!
Your score is 4 moves.
Sample Input 2 Sample Output 2
101628
00
40
60
68
78
95
4
You hit a wumpus!
2
You hit a wumpus!
8
1
You hit a wumpus!
5
You hit a wumpus!
Your score is 6 moves.

Please log in to submit a solution to this problem

Log in