Loading...
$K$개의 독립적인 님(Nim) 변형 게임이 있다. 각 게임은 하나의 돌더미로 구성되며, 해당 게임에서 한 번에 가져갈 수 있는 최대 돌의 수가 정해져 있다. 두 플레이어가 번갈아 가며 임의의 한 게임을 골라 최소 1개, 최대 $m_i$개의 돌을 가져간다. 모든 게임의 돌더미가 0개가 되어 더 이상 가져갈 수 없을 때 마지막 이동을 한 플레이어가 승리한다.
각 돌더미의 그런디 수(Groundy number)는 돌의 개수를 최대 가져갈 수 있는 수로 나눈 나머지인 $n_i \bmod (m_i + 1)$로 계산한다. 이후 모든 게임의 그런디 수를 XOR(배타적 논리합)한 결과가 0이 아니면 선공 필승, 0이면 후공 필승 상태이다. 스프래그-그런디 정리를 이용하여 선공 플레이어의 승패를 판별하라.
첫째 줄에 게임의 수 $K$가 주어진다.
둘째 줄부터 $K$개의 줄에 걸쳐 각 게임의 정보가 한 줄에 하나씩 공백으로 구분되어 주어진다. 각 줄에는 $i$번째 돌더미의 돌 개수 $n_i$와 한 번에 가져갈 수 있는 최대 돌의 수 $m_i$가 순서대로 주어진다.
선공 플레이어가 이기면 WIN, 지면 LOSE를 출력한다.
2
3 2
5 2
WIN
2
2 2
4 2
LOSE