You are entering your robot into a simple game of strategy. The game is played on a grid and the robots take it in turns to move one space at a time (including diagonally) around the grid. When a robot moves into a square, that square is taken and nobody else can move into it for the duration of the game. When a robot is boxed in and cannot move on its turn, it is out. The winner is the Last Robot Standing.
Here's an example of the game in action on a small grid with
In this example, Robot H
, but was not removed from the game at that point. Any robot that is able to move on its turn is safe for that turn. It is only on its next move (Move J
) that it is removed from the game. Note that if Robot
The robots in the above game are choosing their moves from a hardwired "strategy" that tells them the order of moves to try. There are 2481377746543
, and Robot 62437428513
.
On Robot A
), it uses move C
) it uses move E
) it tries move
Using your evil hacking skills, you have found out the strategies of the other robots. Since you get to pick your starting position and you're moving last, you can figure out a winning start position.
The input will contain
Your job is to output a list of starting positions that will lead to a guaranteed win for your robot. If there is no such starting position, you should simply output the word LOSE
. Your output must be formatted exactly as shown below with no extra spaces or punctuation, but the order you output the starting positions for each case can be different from that shown.
Note that the sample input below only contains
Sample Input
5 5 2
3 2
2481377746543
62437428513
3 3 3
1 1
2 2
45362718
45362718
87654321
5 5 3
1 1
3 3
81726354
45362718
12345678
10 10 8
1 3
1 8
3 1
8 1
3 10
8 10
10 3
12345678
87654321
18273645
54637281
21436587
78563412
16372485
73265841
Sample Output
(1,2) (1,3) (2,3) (2,4) (3,1) (4,5) (5,2) (5,5)
(3,3)
(3,2) (4,2)
(1,9) (4,9) (4,10) (5,7) (7,1) (7,2) (7,6) (7,7) (9,4)
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments