eolymp
bolt
Try our new interface for solving problems

Chomp

\textit{\textbf{Chomp}} is two-player strategy game plaed on a rectangular chocolate bar made up of smaller square blocks (cells). The players take turns choosing one block and "eating it" (removing if from the board), together with those that are above it and to its right. The botton left block is \textit{poisoned} and the player who is forced to \textit{eat} it loses. The following diagram shows a game beginning with a \textbf{3}-by-\textbf{3} board. The X indicates the \textit{poisoned} cell. \includegraphics{https://static.e-olymp.com/content/00/008ff7a5554d1b3f387a3a683ab2fbfd2891562a.jpg} A position in the game is a winning position if there is a move that results in a losing position for the opponent. A position in the game is a losing position, if every move from that position either \textit{eats} the \textit{poisoned} square (losing the game) or results in a winning position for the opponent. In the example above, the \textbf{1}×\textbf{1} and equal armed \textbf{L}-shaped positions and losing positions (since the opponent can mirror the current player). The \textbf{3}×\textbf{3}, unequal armed \textbf{L} and \textbf{1}×\textbf{n} positions are winning positions. The aim of this problem is to "solve" \textbf{3}-by-\textbf{100} \textit{\textbf{Chomp}}. That it, for each possible position, determine whether it is a winning or losing position and if it is winning position, give the next move. A position in \textbf{3}-by-\textbf{100} \textit{\textbf{Chomp}}, is determined by the number, \textbf{p}, of squares in the bottom row, the number, \textbf{q}, of squares in the middle row and the number, \textbf{r}, of squares in the top row with: \textbf{100} ≥ \textbf{p} ≥ \textbf{q} ≥ \textbf{r} ≥ \textbf{0} Write a program which, for each possible position in the \textbf{3}-by-\textbf{100} game of \textit{\textbf{Chomp}}, determines whether it is a winning or losing position and if it is a winning position, given the next move (the square to \textit{eat} next). \InputFile The first line of input contains a single integer \textbf{P}, (\textbf{1} ≤ \textbf{P} ≤ \textbf{1000}), which is the number of data sets that follow. Each data set should be processed identically and indenpendently. Each data set consists of a sinle line of input. It contains the data set number, \textbf{K}, followed by the counts \textbf{100} ≥ \textbf{p} ≥ \textbf{q }≥ \textbf{r} ≥ \textbf{0} of squares in the buttom row (\textbf{p}), middle row (\textbf{q}) and top row (\textbf{r}) respectively separated by single spaces. \OutputFile For each data set there is a sinle line of output. If the input position is a losing position, the output line consists of the data set number, \textbf{K}, followed by a sinle space followed by the (captail) letter \textbf{L}. Otherwise (the input position is a winning position), the output consinsts of the data set number, \textbf{K}, followed by the (captail) letter \textbf{W}, followed by the column number and row number of a block to \textit{eat} which results in a losing position for the next player.
Time limit 1 second
Memory limit 64 MiB
Input example #1
4
1 3 3 3
2 3 1 0
3 3 2 0
4 97 64 35
Output example #1
1 W 2 2
2 W 3 1
3 L
4 W 51 1
Source 2013 ACM Greater New York Region, October 27, Problem F