님게임

여러 개의 돌더미에서 두 플레이어가 번갈아 돌을 가져갑니다. 마지막 돌을 가져간 플레이어가 승리합니다.

돌더미는 $N$개이며, 왼쪽부터 $1$번 돌더미에서 $N$번 돌더미까지 번호가 붙어 있습니다. $N$은 $1$ 이상 $10$ 이하이고, 각 돌더미에는 처음에 돌이 한 개 이상 있습니다. 모든 돌더미에 놓인 돌의 수를 합해도 $100$개를 넘지 않습니다. 돌이 모두 사라진 돌더미도 번호는 그대로 유지됩니다.

게임은 선공 A부터 시작하여 A와 B가 번갈아 턴을 진행합니다.

자신의 턴에는 돌이 남아 있는 돌더미 하나를 골라 돌을 한 개 이상 가져갑니다. 한 번에 한 돌더미에서만 가져갈 수 있으며, 그 돌더미에 남아 있는 돌보다 많이 가져갈 수 없습니다.

예를 들어 현재 각 돌더미의 돌 수가 $[3, 1, 4]$일 때, $3$번 돌더미에서 돌을 $2$개 가져가면 $[3, 1, 2]$가 됩니다. $2$번 돌더미에는 돌이 한 개뿐이므로 두 개를 가져갈 수 없습니다.

각 플레이어에게는 게임 전체에서 사용할 수 있는 $1$초의 제한 시간이 주어집니다. 자신의 턴에 행동을 출력하기까지 걸린 시간만 차감되며, 다음 턴이 되어도 남은 시간은 늘어나지 않습니다.

다음 행동은 잘못된 행동입니다.

• 출력 형식에 맞지 않는 문자열을 출력하는 경우
• 존재하지 않거나 돌이 남아 있지 않은 돌더미를 선택하는 경우
• 돌을 한 개보다 적게 가져가거나, 선택한 돌더미에 남아 있는 돌보다 많이 가져가는 경우

잘못된 행동을 한 플레이어는 즉시 패배합니다. 잘못된 행동은 돌더미에 반영되지 않으며, 상대에게 다음 턴이 주어지지 않습니다. 제한 시간 안에 행동을 출력하지 못하거나 프로그램 실행 중 오류가 발생한 경우에도 해당 플레이어가 즉시 패배합니다.

게임은 다음 조건 중 하나가 만족되면 종료됩니다.

• 모든 돌더미에서 돌이 사라졌을 때
• 한 플레이어가 잘못된 행동을 했을 때
• 한 플레이어에게 시간 초과 또는 실행 오류가 발생했을 때

모든 돌이 사라져 게임이 종료되면 마지막 돌을 가져간 플레이어가 승리합니다.

돌더미에 남은 돌의 수를 살펴 마지막 돌을 가져가 최종 승자가 되기 위한 AI를 설계해주세요!

게임을 시작하기 전에 채점기는 두 플레이어에게 동일한 초기 돌더미를 다음 두 줄로 입력합니다.

N
stones_1 stones_2 ... stones_N

• N은 돌더미의 수를 나타내는 $1$ 이상 $10$ 이하의 정수입니다.
• 둘째 줄에는 각 돌더미에 놓인 돌의 수 stones_1, stones_2, ..., stones_N이 공백으로 구분되어 주어집니다.
• 각 돌더미에는 돌이 한 개 이상 있으며, 모든 돌더미에 놓인 돌의 수를 합해도 $100$개를 넘지 않습니다.
• 돌더미 번호는 둘째 줄의 왼쪽부터 $1$번으로 시작합니다.

채점기는 다음의 한 줄 단위로 플레이어와 통신합니다.

• heap_number, take, my_time, opponent_time은 정수입니다.
• heap_number는 $1$ 이상 N 이하이며, 가져갈 돌더미의 번호를 의미합니다.
• take는 $1$ 이상이며, 선택한 돌더미에 현재 남아 있는 돌의 수를 넘을 수 없습니다.
• my_time과 opponent_time은 밀리초 단위로 주어집니다. my_time은 행동 직전 내게 남은 시간이고, opponent_time은 상대가 직전 행동을 마친 뒤 남은 시간입니다.
• OPP는 항상 두 줄로 주어집니다. 첫 줄은 OPP이고, 둘째 줄은 PASS opponent_time 또는 REMOVE heap_number take opponent_time입니다.
• 두 플레이어에게는 게임 전체에서 사용할 수 있는 $1{,}000$밀리초가 각각 주어집니다. READY 응답 시간은 여기에 포함되지 않으며, 자신의 TURN에 응답한 시간만 차감됩니다.
• 채점기는 매 턴 전체 돌더미를 다시 입력하지 않습니다. 자신의 행동과 OPP로 받은 상대 행동을 초기 상태에 차례대로 적용하여 현재 돌더미를 관리해야 합니다.
• 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다.
• 디버그 메시지는 표준 오류에만 출력해야 하며, 표준 출력에는 정해진 응답 외의 문자열을 출력하면 안 됩니다.
• 제한 시간 안에 출력하지 못하면 시간 초과로 즉시 패배합니다. 출력 형식에 맞지 않는 문자열이나 올바르지 않은 행동을 출력한 경우에도 즉시 패배하며, 해당 행동은 상대에게 OPP로 전달되지 않습니다.

초기 돌더미가 $[2, 1]$인 경기에서 다음과 같이 통신할 수 있습니다. 아래 표에서는 두 플레이어에게 공통으로 주어지는 초기 상태 두 줄을 생략합니다. 표의 시간 값은 설명을 위한 예시입니다.

• CPP20 : main.cpp
• PYTHON3, PYPY3 : main.py