Battle of Two Geniuses
InterviewTime limit2sMemory limit512 MB
Given a sequence of tic-tac-toe moves, print after each prefix whether the first player wins, the second player wins, or the game is a draw under optimal play.
- Level
Medium4 of 10
- Topics
- Game theory, Brute force, Recursion
- Solved
- No attempts yet
Problem
In the Season 3 final, Jang Dong-min lost to Oh Hyun-min in "this game". That was his last loss.
In Season 4, the two met again in "this game". Jang Dong-min won two games in a row against Oh Hyun-min and won the revenge match convincingly.
Verify how perfect his play was.
Input
The first line contains the number of moves N.
Each of the next N lines contains a record of "this game". The game may or may not have ended. See the examples.
There are 4 input data sets in total.
Output
Print N lines.
On line k, print the result after the first k moves, assuming both players play optimally: + if the first player wins, - if the second player wins, and 0 if the game is a draw.
The whole test data is judged. Printing correct answers for 0.in earns 2 points, and printing correct answers for 1.in, 2.in, and 3.in earns 332748117 points each.