|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
C - Runner Pawns
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
The “Runner Pawns” game is a variant of classic Chess for a single player. It uses a board similar to the chess board, divided in $8 \times 8$ squares. As in chess, each square can contain only one piece at a time. The pieces are a number of pawns (the “Runner Pawns”), and a single horse, which is the only piece under command of the player. The objective is to capture all pawns before they get to the last row and become kings.
Horse moves are said to be in $\texttt{‘L’}$ shape, since a horse must always move two squares in one direction and one square in the perpendicular direction. The figure above illustrates horse movements, where the character $\texttt{‘H’}$ indicates the horse current position, and the character $\texttt{‘•’}$ indicates possible final positions. Notice that in the representation used black and white squares of the chess board are not distinguished.
Pawns’ moves are a bit different from chess, since they can only move one square forward, and all of them move at the same time. They never move on a diagonal. Squares of the board are numbered from $1$ to $64$, as shown above. Pawns move in vertical direction from top to bottom, so that squares numbered $57$ to $64$ are the pawns’ goal.
Each round of the game is composed by one move of the horse followed by a simultaneous move of all pawns not yet captured.
In order to capture a pawn, the player has to move the horse to a square where a pawn is. A captured pawn leaves the board, and only the remaining ones will move ahead in the next round. To win the game, the player has to capture all pawns. If a pawn gets to the last row, it becomes a king. Then the horse has only one more move to capture it. If it doesn’t, the king moves and it means that the game is over and the player loses. Moreover, if the horse moves to a square that will be occupied by a pawn at the next move of the pawns, the horse is captured by the pawn and the player loses.
Your task is to write a program that analyses a “Runner Pawns” diagram and answer whether there is a sequence of movements for the horse to win. If it is possible, your program should determine the minimum number of moves needed by the horse to capture all pawns.
Input
The input contains several instances of the problem, one per line. Each instance starts with an integer $P$ representing the number of pawns $(0 \leq P \leq 8)$, followed by $P$ integers $(1 \leq A_1, A_2, ... A_P \leq 64)$ that describe the initial position of each pawn, followed by an integer $H$ $(1 \leq H \leq 64)$ representing the starting position of the horse. The end of input is indicated by a line containing $P = 0$.
Output
For each instance of the problem in the input your program must print a single line, containing the answer to the problem. If there is a sequence of moves for the horse to capture all pawns before a surviving king moves (and without the horse being captured by a pawn) then the program should print the length of the minimum sequence of moves that make it possible. Otherwise your program should print the word $\texttt{‘impossible’}$.
Sample test(s)
Input
1 1 11
1 60 1
2 33 60 54
0
Output
1
impossible
3