11534  Say Goodbye to TicTacToe
Moderator: Board moderators
Re: 11534  Say Goodbye to TicTacToe
If you don't know about grundy number, you should learn it.
Lee, Taeyoon
Re: 11534  Say Goodbye to TicTacToe
I am getting WA in this prob. Anyone please check the following cases or give any tricky case.
Input
Output
Input
Code: Select all
12
..
........................
.....X...O....XO
.
...XOXOXOXO
...X..........O...X....O..O.....X....XO
XOXO
...XOX
............................................................
XOXOXOXOXOXOXOXOXO........................................
XOXO.......XOXO
X....O....X
Code: Select all
Impossible.
Impossible.
Possible.
Possible.
Possible.
Possible.
Impossible.
ImPossible.
Impossible.
Possible.
Impossible.
Possible.
Re: 11534  Say Goodbye to TicTacToe
I get the same answers as you do.
Re: 11534  Say Goodbye to TicTacToe
>>baodog
thx for ur help. Now i have got AC.. Silly mistake in my coding..
thx for ur help. Now i have got AC.. Silly mistake in my coding..

 New poster
 Posts: 20
 Joined: Mon Oct 20, 2008 6:26 am
Re: 11534  Say Goodbye to TicTacToe
Can anyone tell me how to handle this input with SG function?
..O.X.
The answer should be "Possible."
..O.X.
The answer should be "Possible."
Re: 11534  Say Goodbye to TicTacToe
suppose u r playing 3 nim games here
1. ..O
2. O.X
3. X.
each game canbe represented by three values.first length of the game , second value on the left side and third value on the right side. for each game u can place a X or O in positions from 0 to len1 and split the game into 2 subgames.The grundy number for each game is simply the xor of the both subgames grundy number.u must take special care about the terminal positions.
hope this helps..
1. ..O
2. O.X
3. X.
each game canbe represented by three values.first length of the game , second value on the left side and third value on the right side. for each game u can place a X or O in positions from 0 to len1 and split the game into 2 subgames.The grundy number for each game is simply the xor of the both subgames grundy number.u must take special care about the terminal positions.
hope this helps..
Last edited by mmonish on Tue Oct 21, 2008 4:25 pm, edited 1 time in total.

 New poster
 Posts: 20
 Joined: Mon Oct 20, 2008 6:26 am
Re: 11534  Say Goodbye to TicTacToe
Can you print the SG function for these three subgame? I think it maybe more than 1.
Re: 11534  Say Goodbye to TicTacToe
>>SerailHydra
SG value for this trree subgames are 2,0and 1.
>>Leonid
I don't know is there any similar probs in UVA.But u can try this prob https://www.spoj.pl/problems/TRIOMINO/ in spoj.it is quite similar this one..
SG value for this trree subgames are 2,0and 1.
>>Leonid
I don't know is there any similar probs in UVA.But u can try this prob https://www.spoj.pl/problems/TRIOMINO/ in spoj.it is quite similar this one..
Re: 11534  Say Goodbye to TicTacToe
Can anyone explain me thoroughly how to solve this problem with grundy number? Please....