님 게임 변형 (Misère)

문제

N개의 돌 더미가 있다. 두 명의 플레이어가 번갈아 가며 턴을 진행하고, 각 턴에서 현재 플레이어는 하나의 더미를 골라 그중 1개 이상의 돌을 가져간다. 더 이상 가져갈 돌이 없어서 마지막 돌을 가져가는 플레이어가 지는 님 게임의 변형(Misère Nim)이다.

두 플레이어가 모두 최적의 전략으로 플레이할 때, 선공 플레이어가 승리하는지 판별하는 프로그램을 작성하라.

제한

• 1 ≤ N ≤ 100
• 1 ≤ 각 더미의 돌 개수 ≤ 109