| MAIN Home Schedule Registration Rules About Language RESULTS Standings Problem Set LINKS LSU Computer Science Contest Index HS 2000 ACM Intl PC PC2 THANKS Sponsor Schools Volunteers | Complete Tic-Tac-ToeProblem: A certain crazy mathematician (who shall remain anonymous) liked to spend a lot of his time coming up with totally useless puzzle games that only other crazy mathematicians could appreciate. He spent a good part of his life (about 15 years or so) trying to develop a Generalized Theory of N Dimensional Tic-Tac-Toe Spaces. Unfortunately, our mathematician friend was somewhat stereoscopically challenged (no depth perception) and could never develop the theory past 2 dimensions. Instead, he came up with a variation of the normal Tic-Tac-Toe game called Complete Tic-Tac-Toe. This game works just like the original that we all know and love with one exception: players keep drawing X's and O's until all nine spaces of the board are completely filled up. This gives rise to four possible outcomes of the game: player X wins, player O wins, both players win, or neither one wins.As a former student of the late mathematician, you decided to continue his work and write a program that computes the outcome from any given game of Complete Tic-Tac-Toe. Input The first line of the input will contain an integer between 0 and 1000 inclusive that indicates how many different games of Complete Tic-Tac-Toe your program will examine. Following that are 9 lines for each game of Complete Tic-Tac-Toe with one number per line (to make things simple, O's are represented as 0's (zeroes) and X's are represented by 1's (ones). Output For every game of Complete Tic-Tac-Toe examined, the program should print one of the following indicating the outcome of the game: X Wins, O Wins, Both Win, or No One Wins. The outcome of each game should be printed on a separate line. The same symbol (i.e. 1 or 0) appearing three times in a row, column, or diagonal is considered a win. If there is one and only one such row/column/diagonal for X and none for O then X is the winner. Likewise, if there is one and only one such row/column/diagonal for O and none for X then O is the winner. If both X and O each have one row/column/diagonal then both are declared the winners. Otherwise, no one wins. Note: Consider all the possible TicTacToe boards you can draw that have at least one winning position. Sample Input 3 number of games 1 row 1 col 1 (x) - first game 0 [1,2] (o) 1 [1,3] (x) 0 [2,1] (o) 1 [2,2] (x) 0 [2,3] (o) 1 [3,1] (x) 1 [3,2] (x) 0 [3,3] (o) 1 [1,1] (x) - second game 1 [1,2] (x) 0 [1,3] (o) 1 [2,1] (x) 0 [2,2] (o) 0 [2,3] (o) 1 [3,1] (x) 1 [3,2] (x) 0 [3,3] (o) 0 [1,1] (o) - third game 1 [1,2] (x) 0 [1,3] (o) 0 [2,1] (o) 0 [2,2] (o) 1 [2,3] (x) 1 [3,1] (x) 0 [3,2] (o) 1 [3,3] (x) Note: The items in italics are here to help you understand the data. Your real input will only have the numbers. Sample Output X Wins Both Win No One Wins |