님 게임 홀짝
시간 제한2초메모리 제한512 MB
짝수 개를 가져가면 돌을 남기고 홀수 개를 가져가면 더미를 비워야 하는 홀짝 님에서 선공이 이기는지 판정합니다.
문제
koosaga와 cubelover가 님 게임의 홀짝 변형을 한다. 돌을 위로 쌓아 만든 돌 더미가 개 있고, 각 더미에는 돌이 한 개 이상 있다. 두 사람은 턴을 번갈아 진행한다. 자기 턴에는 돌이 남아 있는 더미 하나를 고르고, 그 더미에서 돌을 한 개 이상 제거한다.
돌을 제거하는 규칙은 두 가지다.
- 짝수 개를 제거할 때는 그 더미의 돌을 모두 제거할 수 없다. 예를 들어 더미에 돌이 8개 있으면 2개, 4개, 6개만 제거할 수 있고 8개는 제거하지 못한다.
- 홀수 개를 제거할 때는 그 더미의 돌을 모두 제거해야 한다. 그래서 돌이 8개인 더미에서는 홀수 개를 제거하는 수가 없고, 돌이 7개인 더미에서는 2개, 4개, 6개, 7개만 제거할 수 있다.
이 규칙 때문에 돌이 0개 또는 2개 남은 더미에서는 더 이상 돌을 제거하지 못한다. 모든 더미의 돌이 0개 또는 2개가 되면 게임이 끝나고, 마지막으로 돌을 제거한 사람이 이긴다.
게임은 koosaga가 먼저 시작한다. 두 사람이 최적으로 진행할 때 이기는 사람을 구한다.
입력
첫째 줄에 돌 더미의 개수 이 주어진다. ()
둘째 줄에 각 더미에 쌓인 돌의 개수 이 공백으로 구분되어 주어진다. ()
모든 가 2인 입력은 주어지지 않는다.
출력
koosaga가 이기면 koosaga를, cubelover가 이기면 cubelover를 첫째 줄에 출력한다.