Sphere Online Judge

Maintanance
Because of maintenance, it is currently impossible to submit any solutions. The maintenance will end around 3:00 am GMT (4:00 am SPOJ time).

This message will disappear once the maintenance is finished.


SPOJ Problem Set (classical)

13303. Tic-tac-toe 3

Problem code: OVOXO

Bored to death working at the Byteland Office...your colleagues have resorted to game of crosses Xs and naughtd Os or Tic-tac-toe. One of them keeps on losing and is tired of the jokes. He plans to have an Android app in his phone to help him out. He is your good friend and seeks your assistance. "Treat at ANC is guaranteed", he says.

He also is very frugal when it comes to memory usage. So please don't write a long if else chain...cause you have to do the task within 999 bytes

Input

An integer T - the number of test cases. (T<1000). T test cases follow.

Each test case comprises 3 strings each separated by newline and containing exactly 3 characters(either 'X','O' or '_') per line. An empty line follows each test case. Each input position is guaranteed to be a valid tic tac toe position such that the game is still not over.

Output

For each test case print "WON" if it is a sure shot winning position. Else print "CONTINUE". Then output the game after having made your move. If more than one move are equally good try playing the move on the first empty spot.

Example

Input:

2
OOX
OX_
__X

XX_
XOO
_O_

Output:

WON
OOX
OXX
__X
WON
XXX
XOO
_O_

Info

1) iguaranteed always to be X's move (it is the standard) and whose move it currently is can be computed... 
2) winning position is meant for the current player 
3) winning in lesser number of moves is better and drawing is better than losing as in general AI 
4) you need to print the board as it looks after making the best move 
5) print WIN if the current player can win in the case when both players play optimally from here on... 
__X

Added by:Aditya Pande
Date:2013-01-14
Time limit:1s
Source limit:999B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:TOE2

hide comments
2013-01-19 05:58:00 Aditya Pande
@mitch: my mistake forced win in 3 moves is possible...
Also I have added a few stronger test cases...and rejudged all submissions

Last edit: 2013-01-19 05:53:13
2013-01-19 05:58:00 Mitch Schwartz
Ok thanks for clarifying Robert and Aditya, but you gave slightly different rules, so it seems likely the test data is weak!

Based on Aditya's rules, we should then also prefer a 2-move loss over a 1-move loss (and so on), is that right? This is not "standard", it's just one possible definition of what constitutes optimal play. Another entirely acceptable definition is to treat all winning moves (for example) as equally good, regardless of how long it takes to get there.

It's an interesting twist, and I'm examining my approach to see whether it can be modified accordingly. Although I get the feeling I'm analysing the problem more carefully than the problem setter did. :P

Edit: Well, I got AC under the assumption that in a winning position we try to win as fast as possible, and in a losing or drawn position we try to lose/draw as slowly as possible.

--> The test cases are weak. I agree and I will add stronger ones ...but not now...
Hope the problem did make you think....:)
--->Edit( ADITYA ):- Draw cannot be fast or slow...

Yes you're right, in this game draw can't be fast or slow, anyway in my implementation the piece of code that deals with it handles case of draw and lose simultaneously.

Last edit: 2013-01-18 08:45:49
2013-01-19 05:58:00 Mitch Schwartz
Description not really clear.

(1) Is it guaranteed always to be X's move?
(2) If not: Does "winning position" mean winning for the person whose turn it is now, or winning for X?
(3) "equally good" is not defined -- is winning in 1 move considered better than winning in 2 moves, or are they equal? Robert Gerbicz also commented about this, but I can't tell from his comment which option we are required to print.
(4) If it is not a winning position, do we still need to choose and print the next move? And if so, presumably we should choose a drawing move over a losing move?

Also, I think it's an easier version of MYQ8. :p

ans (Gerbicz): X is the first player in every game (this is the standard tic-tac-toe), but it is possible that the current turn is for the "O" player.
(2) print WON, if it is winning for the current player, who takes the move.
(3) Winning in 1 move is better than winning in 2 or more moves. But going higher this is not true, so say winning in 2 moves is NOT better than winning in 3 moves.
(4) Choose (and print!) the better move so for example the drawing move over the losing move. And in these cases still choose the first such move.

Edit( ADITYA ):
@Robert thank you for the explanation
@Mitch: sorry for the ambiguity
1) it is the standard and whose move it currently is can be computed...
2) winning position is meant for the current player
3) winning in lesser number of moves is better and drawing is better than losing as in general AI
4) you need to print the board as it looks after making the best move
5) print WIN if the current player can win in the case when both players play optimally from here on...

also MYQ8 seems much easier than this...
if nothing comes to the mind, it can be solved by a long chain of if else...
i shall try it later :p


Last edit: 2013-01-19 05:45:21
2013-01-19 05:58:00 Robert Gerbicz
When should we print "WON"? I print when there is a winning move and after it the game is over. And in this case I choose the move that comes first. Is it a correct interpretation?
-->no ( if a win can be forced print WON)
--->congrats you are the first one to solve it...

Last edit: 2013-01-14 18:37:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.