문제

틱택토 게임(Tic-Tac-Tok)은 $3\times 3$ 격자 위에서 두 플레이어가 즐기는 게임이다. 두 플레이어가 격자 위에 번갈아가며 O와 X를 두며 가로/세로/대각선 중 어느 한 방향으로 3개가 이어지면 승리한다. 틱택토 게임은 여기서 플레이해볼 수 있다.

틱택토 게임은 두 플레이어가 최선의 전략을 사용할 경우 절대로 한쪽이 승리할 수 없고 무승부가 나는 제로섬 게임이다.

이 문제는 인터랙티브 문제다. 인터랙티브 문제란 문제에 대한 답을 단순히 출력하는 것이 아니라, 채점기와 상호작용하여 정답을 알아내는 문제다.

이 문제에서 여러분은 채점기와 틱택토를 하여 무승부를 내는 프로그램을 작성해야 한다.

인터랙티브

입출력의 편의를 위해 각 칸에는 위 그림과 같이 번호가 매겨져 있다.

게임은 다음과 같이 진행된다.

• 채점기 턴: 한 줄에 하나의 정수 $A$가 주어진다. ($-1\le A\le 9; A\neq 0$)
  • $A\ge 1$: 채점기가 $A$ 위치에 X를 두었다는 의미다.
  • $A= -1$: 여러분의 프로그램이 직전에 잘못된 위치에 두었거나, 채점기가 이번 턴에 승리하는 수가 존재한다는 의미며 틀렸습니다를 받는다. 이때 여러분의 프로그램은 즉시 종료되어야 한다. 그렇지 않으면 예상하지 못한 결과를 얻을 수 있다.
• 여러분의 턴: 여러분의 프로그램은 한 줄에 하나의 정수 $B$를 출력해야 한다. ($1\le B\le 9$) 여러분의 프로그램이 $B$ 위치에 O를 두었다는 의미다.

처음에는 채점기 턴부터 진행된다. $3\times 3$ 격자를 모두 채웠음에도 승부가 나지 않았다면 프로그램을 종료해야 하며 맞았습니다를 받는다.

채점기는 항상 최선의 수를 두는 것이 보장된다.

5

1

4

-1

 
2

9

6

입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해, 의도적으로 줄 간격을 조절한 것이다. 실제 입출력과 다른 것에 유의하자.

여러분의 프로그램이 6을 출력한 이후 채점기는 7을 출력하여 게임에서 승리할 수 있다. 따라서 -1가 출력되었고 여러분의 프로그램은 즉시 종료되어야 한다.

5

6

7

2

9

 
1

4

3

8