XO
InterviewTime limit1sMemory limit1024 MB
Given the first N moves of a tic-tac-toe game, decide whether X or O moves next, whether X or O has won, or whether the game is a draw.
- Level
Easy2 of 10
- Topics
- Implementation, Simulation
- Solved
- No attempts yet
Problem
Križić-kružić is a game for two players. For those who do not know the rules, here is a short summary. Two players fill a table with nine empty cells arranged in three rows and three columns. Player X writes the letter X and player O writes the letter O. Starting with X, the players take turns choosing an empty cell and writing their mark in it. A player wins by writing three of their marks in a line: a row, a column, the main diagonal, or the anti-diagonal. The game ends at that moment. If no one manages this and all cells are filled, the game ends with no winner. For example, the figure shows seven moves that led to a win for the first player.
You are given a real game that has been played for N moves. Write a program that determines what follows the N-th move. The possible answers are:
- Player X continues the game by placing their mark in an empty cell.
- Player O continues the game by placing their mark in an empty cell.
- The game ended with a win for player X.
- The game ended with a win for player O.
- The game ended with no winner because no empty cells remain.
Input
The first line contains an integer N (0 ≤ N ≤ 9), the number of moves played.
Each of the next N lines contains a natural number P (1 ≤ P ≤ 9), the cell number where the player on turn wrote their mark. The top left cell is numbered 1 and the bottom right cell is numbered 9. See the figure in the problem statement.
Output
Print one natural number from 1 to 5 on a single line, the number of the possibility from the problem statement.
Hint
After three moves, it is player O's turn. After seven moves, the game ended with a win for player X. After nine moves, no empty cells remain and no one won, so the game ended with no winner.
