돌
시간 제한3초메모리 제한512 MB
상대가 고른 더미에서 몇 개를 가져갈지 정하는 방식으로 진행되는 돌 가져가기 게임에서, 먼저 더미를 지목하는 안키차가 이기는지 판정한다.
문제
Ankica가 마침내 Branko를 붙잡았지만, Branko는 신문을 사 주기를 거부하고는 지난번 게임은 조작되어 있었으니 다른 게임을 하자고 요구했다. Ankica는 순진하게도 돌을 이용한 또 다른 게임을 제안했지만, Branko는 당연히 의심하여 게임의 규칙을 완전히 바꾸기로 했다.
게임에는 개의 돌 더미가 있고 번째 더미에는 개의 돌이 있다. 플레이어들은 번갈아 가며 한 더미에서 몇 개의 돌을 가져간다. 마지막 돌을 가져간 플레이어가 이긴다.
문제는, 특정 턴에 플레이어가 돌을 가져가야 하는 더미를 상대 플레이어가 지정한다는 점이다.
더 정확히 말해, 턴의 번호가 1부터 증가하는 정수로 매겨질 때 게임은 다음과 같이 진행된다.
- 홀수 번째 턴은 Branko가 비어 있지 않은 돌 더미를 가리키면서 시작한다. 그러면 Ankica가 그 더미에서 돌을 최소 하나, 최대 전부까지 가져간다.
- 짝수 번째 턴은 Ankica가 비어 있지 않은 돌 더미를 가리키면서 시작한다. 그러면 Branko가 그 더미에서 돌을 최소 하나, 최대 전부까지 가져간다.
Branko는 돌을 모아 몇 개의 더미를 만들었고, 둘은 게임을 시작했다. 프로 게이머인 Ankica는 시작 상태가 자신의 승리 상태, 즉 Branko가 남은 게임을 어떻게 두더라도 자신이 이길 수 있다는 것을 금방 알아차렸다.
Ankica의 입장에서 게임을 이길 수 있겠는가?