Thou Last , Thou LosethProblem code: KC203 |
All submissions for this problem are available.
Points:10
One of the favourite games of the Brotherhoood of Brom went by the name of Thou Last , Thou Loseth . The game was played on a 5 by 5 board. Initially every array cell had a piece in it. Two players removed pieces alternatively from the board. The player could 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 could either remove one piece (A1, A2, or B1), or remove two pieces (A1 and A2, or A1and B1) simultaneously. The game would end when one player was forced to take the last piece, making the other player win 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 0You think this game would make a wonderful summer project at college. But wait, why not go one step ahead in the spirit of your greatest grandfather s genius. You will create 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''.
Note that during the game tree evaluation, if the current configuration has a winning move, then it is not necessary to search any further because the configuration is guaranteed to be winning. This can greatly reduce the game tree search time.
Input:
The first line consists of total no of test cases T(<50).The next 5T lines will consist of the configuration of each test case.
Output:
Output is a string "winning" OR "losing"
Example:
Input:3 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Output:
winning losing winning
| Author: | ankitbabbar |
| Date Added: | 16-10-2009 |
| Time Limit: | 5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Hey, can I get some more
Hey, can I get some more sample inputs for this problem
Will the player always make
Will the player always make the first move
@ mohit :if the game needs to
@ mohit :if the game needs to be played, a player will make a move..
In the first sample input
In the first sample input given above, if player does not make first move, the opponent will win. And from problem statement, it is not clear if the player always makes first move.
If opponent can make first move, then please explain first sample input and its output.
@Ankit: can I get some more
@Ankit: can I get some more sample inputs for this problem
the first test case: player 1
the first test case:
player 1 chooses A1,A2
so player 2 will be forced to choose B1 which is the last move..hence player 1 had the winning move..
the second test case:
suppose player 1 chooses E1,E2,E3 then it is a losing move from him as player 2 will then choose either A1,A2 or C1,C2 ..and either case player 1 will make the last move and hence he loses...as there was no such winning move from him...
wat wud b output for
wat wud b output for following config
0 1 1 1 1
0 0 0 0 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
@Ankit: Reply fast is u r
@Ankit: Reply fast is u r thr
Time is running out....
the output will be winning
the output will be winning for both the cases..
Thnks man....
Thnks man....