# [Platinum III] 님 게임 홀짝 [문제 링크](https://www.acmicpc.net/problem/11871) ## 문제 설명 <p>koosaga와 cubelover가 님 게임 홀짝 버젼을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. </p> <p>일반적인 님 게임과는 다르게 님 게임 홀짝은 돌을 제거할 때 규칙이 있다. 짝수 개수만큼 돌을 제거하는 경우에는 돌 더미에 있는 돌을 모두 제거할 수 없다. 예를 들어, 한 돌 더미에 있는 돌의 개수가 8개인 경우에는 2, 4, 6개만 제거할 수 있다. (8개는 제거할 수 없다) 돌을 홀수 개수 만큼 제거하는 경우에는 돌 더미에 있는 돌을 모두 제거해야한다. 예를 들어, 돌의 개수가 8개인 경우에는 홀수 개수 만큼 돌을 제거할 수 없으며, 돌의 개수가 7개인 경우에는 2, 4, 6, 7개만 제거할 수 있다.</p> <p>각 돌 더미에 돌이 0개 또는 2개 남은 경우에는 더 이상 돌을 제거할 수 없으며, 모든 돌 더미에 돌이 0개 또는 2개 남은 경우에 게임이 끝난다. 이때, 마지막 돌을 제거하는 사람이 게임을 이긴다.</p> <p>게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.</p> ## 입력 <p>첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 100)이 주어진다.</p> <p>둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 P_i (1 ≤ P_i ≤ 2,147,000,000)가 주어진다. 모든 P_i가 2인 경우는 입력으로 주어지지 않는다.</p> ## 출력 <p>koosaga가 이기는 경우에는 'koosaga'를, cubelover가 이기는 경우에는 'cubelover'를 출력한다.</p> ## 풀이 $g(0)=0$ $g(1)=mex(g(0))=1$ $g(2)=0$ $g(3)=mex(g(0), g(1))$ $\vdots$ $g(2n)=mex(g(2), g(4), ..., g(2n-2))$ $g(2n+1)=mex(g(0), g(1), g(3), ..., g(2n-1))$ 이렇게 그런디수가 형성되어 나머지는 님 게임과 동일하게 입력으로 들어오는 모든 수의 그런디수를 xor하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int g=0; while(n--) { int p; cin >> p; if(p%2) g ^= (p+1)/2; else g ^= p/2-1; } cout << (g ? "koosaga" : "cubelover"); } ```