Bill is fond of computer games. He likes to analyze games and to provide efficient
solutions. Now, he is studying the following game. The game starts with a n x n matrix filled with
positive integers. When it is her/his turn, a player can delete the last row or the last column of the
matrix, if the sum of the numbers in that row/column is even. If a player cannot delete the last row
or the last column on his turn, then he loses the game. Bill thinks that this game can be classified
as first player wins (W) or first player loses (L). First player wins means that the first player has a
strategy to win, no matter how the second player plays the game. First player loses means that
no matter what the first player does the second player has a strategy to win.
Bill is also a skilled programmer. He wants to write a program to classify the game
quickly. Can you help him?
The program input is from a text file. Each data set in the file stands for a particular
game. A data set starts with the number n (n <= 1000), the matrix dimension, followed by the
positive integers in the matrix. The program has to print W if the first player wins the game, or L if
the first player loses the game.
White spaces can occur freely in the input. The input data are correct and terminate with
an end of file. For each set of data the program prints the result to the standard output from the
beginning of the line. An input/output sample is in the table bellow. There are two data sets. In the
first case, the matrix dimension n is 2. The integers in the matrix are: 2 4 6 8. The result for the
data set is L, meaning that no matter what the first player does, the second player wins.
2 2 4 6 8 3 5 4 2 1 5 9 7 3 8
L W
Migrated from old NTUJ.
SEERC 2010
| No. | Testdata Range | Score |
|---|