REMGAME - Stone Removing Game
Consider the following game. The game is played on a 5 x 5 board. Initially every array cell has a piece in it. Two players remove pieces alternatively from the board. The player can remove any number of consecutive pieces in a row or column. For example, in the configuration depicted below where one indicates a piece, the player can either remove one piece (A1, A2, or B1), or remove two pieces (A1 and A2, or A1 and B1) simultaneously. The game ends when one player is forced to take the last piece, and the other player wins the game.
1 | 2 | 3 | 4 | 5 | |
A | 1 | 1 | 0 | 0 | 0 |
B | 1 | 0 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 0 | 0 |
D | 0 | 0 | 0 | 0 | 0 |
E | 0 | 0 | 0 | 0 | 0 |
Write a program that evaluates board configurations from this game. The program must output "winning" when there exists a winning move that no matter how the opponent responds, it will force the opponent to take the last piece. Otherwise, the program must output "losing".
Input
The first line contains n, the number of test cases. For each test case, a 5x5 grid of an initial game configuration is shown.
Output
For each case, output "winning" or "losing".
Example
Input: 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 Output: winning
hide comments
narek:
2018-09-05 18:33:41
@amaroq weak test cases, I tread to implement it bottom up and got many tles, the recursive approach worked fine for me |
|
amaroq:
2009-05-16 05:29:37
Either the number of cases is very small or the the input is very simple, or both, because a runtime of 0.01 seconds is ridiculous. |
Added by: | Chen Xiaohong |
Date: | 2007-11-13 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Adapted from Taiwan TPC 1999, Harder datasets. |