Recently I came across the following problem in a contest. We tried the problem for a long time, but could not come up with a correct solution.
Alice and bob are playing a game across $$$ n \leq 10000 $$$, 3×3 Tic-tac-toe boards with both players marking the board with X. Each board already has some X's on it. One player can choose an arbitrary board and put an X on any of the empty cells. Alice always makes the first move. You can not make any further moves on a board after it has three consecutive X's (column, row or diagonal). A game ends when all the boards contain three consecutive X's. The player that made the last move loses the game.
Given a configuration of the game, you have to find out the winner. It is given that none of initial boards contain three consecutive X's.
Sample Input:
5
1
XX.
..X
..X
1
..X
X..
X.X
1
..X
.X.
.X.
1
..X
X..
XX.
1
..X
X..
..X
Sample Output:
Game #1: Alice
Game #2: Alice
Game #3: Bob
Game #4: Bob
Game #5: Bob
