격자 게임

NYPC 2020 · 예선

모스와 우니는 다음과 같은 턴 방식 게임을 하려고 한다. 첫 턴은 모스의 턴이다. 처음에 아래 그림과 같은 3행의 격자칸이 주어진다. 3행 중 1행에 ii 개의 칸, 2행에 jj 개의 칸, 3행에 kk 개의 칸이 왼쪽으로 붙어있다.

처음에 주어질 때 0ijkN0 \le i \le j \le k \le N임과 k>0k \gt 0임이 보장된다. 즉, 각 행의 칸 수는 아래 행으로 갈 때 줄어들지 않는 식이다.

매 턴에서 모스와 우니는 현재 존재하는 칸 중 어떤 칸이든 선택할 수 있다. 예를 들어, 아래 그림에 X로 표시한 칸을 선택할 수 있다.

그러면, 선택한 칸, 선택한 칸의 오른쪽 모든 칸, 선택한 칸의 위쪽 모든 칸, 선택한 칸의 오른쪽 위 모든 칸이 사라진다. 즉, 아래 그림과 같은 상태가 된다.

게임의 규칙은 자신의 턴에서 제일 왼쪽 아래, 즉 3행의 1번째 칸을 선택하는 사람이 지는 것이다.

당신은 모스의 역할을 하는 프로그램을 짜야 한다.

입력과 출력

이 문제는 대화형(interactive) 문제이다. [연습문제] UP & DOWN을 우선 풀어보는 것도 좋을 것이다.

처음 격자의 상태는 표준 입력(stdin)으로 한 줄에 ii, jj, kk의 값이 공백을 사이에 두고 주어진다. (N100;(N\le 100; 0ijkN;0 \le i \le j \le k \le N; k>0)k \gt 0) 당신의 프로그램은 우선 이 값들을 읽어야 한다.

우니가 어떤 전략을 사용하든 모스가 이길 수 있는 전략이 있는 입력만 주어짐이 보장된다.

당신의 프로그램이 어떤 칸을 선택할 지 결정한 후 그 칸을 행 번호와 칸 번호의 쌍으로 한 줄에 공백을 사이에 두고 출력해야 한다.

주최측의 프로그램은 당신의 선택에 따라 스스로 선택을 한 후 그 선택을 당신의 프로그램의 표준 입력으로 동일한 방식으로, 즉, 행 번호와 칸 번호의 쌍으로 한 줄에 공백을 사이에 두고 줄 것이다. 당신의 프로그램은 표준 입력으로 이 값들을 읽어야 한다.

예시 대화

A, B, C = readline_int_tuple() // read 2 3 6, 초기 게임판의 상태를 입력받음
printline "3 6" to stdout      // 프로그램이 (3, 6)을 선택. 게임 상황이 2 3 5로 바뀜
p, q = readline_int_tuple()    // read 3 5 주최 측 프로그램이 (3, 5)를 선택. 게임 상황이 2 3 4로 바뀜
printline "1 1" to stdout      // 프로그램이 (1, 1)을 선택. 게임 상황이 0 3 4로 바뀜
p, q = readline_int_tuple()    // read 3 4 주최 측 프로그램이 (3, 4)를 선택. 게임 상황이 0 3 3로 바뀜
printline "2 3" to stdout      // 프로그램이 (2, 3)을 선택. 게임 상황이 0 2 3로 바뀜
p, q = readline_int_tuple()    // read 3 3 주최 측 프로그램이 (3, 3)를 선택. 게임 상황이 0 2 2로 바뀜
printline "2 2" to stdout      // 프로그램이 (2, 2)을 선택. 게임 상황이 0 1 2로 바뀜
p, q = readline_int_tuple()    // read 3 2 주최 측 프로그램이 (3, 2)를 선택. 게임 상황이 0 1 1로 바뀜
printline "2 1" to stdout      // 프로그램이 (2, 1)을 선택. 게임 상황이 0 0 1로 바뀜
p, q = readline_int_tuple()    // read 3 1 주최 측 프로그램이 (3, 1)를 선택. 게임이 프로그램의 승리로 끝남
exit                           // 게임이 끝난 이후, 더이상 출력하지 않고 프로그램을 정상 종료하여야 함

주의 사항

당신의 프로그램의 선택을 행 번호, 칸 번호로 한 줄에 출력할 때 반드시 줄을 끝맺는 문자(줄 바꿈 문자)를 같이 출력해야 한다.

게임이 끝난 경우, 즉, 당신의 프로그램이 3 1을 출력했거나, 주최 측 프로그램이 3 1을 출력한 경우, 더이상 다른 내용을 출력하거나 읽지 않고 프로그램을 종료하여야 한다.

출력을 한 이후에는 내부 버퍼에 출력 내용이 쌓여 주최 측 프로그램에 전달되지 않을 수 있으니, 이를 피하기 위해 반드시 출력할 때마다 flush 연산을 해서 출력 버퍼를 비워야한다. C에서는 fflush(stdout), C++에서는 cout.flush() 혹은 cout << flush, C#에서는 Console.Out.Flush(), Java에서는 System.out.flush(), Python에서는 sys.stdout.flush()를 통해 flush 연산을 할 수 있다.

채점 방식

여러분이 작성한 프로그램은 항상 이겨야 한다. 여러분의 프로그램이 현재 존재하지 않는 칸을 선택하거나, 제한 시간을 초과하거나, 제일 아래 행 제일 왼쪽 칸을 선택하면 진다. 제한 시간은 당신의 프로그램이 실행되는 시간에 대해서만 적용된다. (주최 측 프로그램이 실행되는 시간은 포함되지 않는다.) 또, 제한 시간은 당신의 프로그램이 실행된 시간 전체에 대해 적용된다. 즉, 한 턴에서 계산하는 시간에 대한 제한이 아니다.

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 30

N10N \le 10.

종류 2: 70

추가적인 제한 조건이 없음.

해설