# [Platinum III] 핌버 [문제 링크](https://www.acmicpc.net/problem/16877) ## 문제 설명 <p>koosaga와 cubelover가 "핌버"를 하고 있다. 핌버는 님 게임에 규칙을 추가한 게임이다. 핌버는 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 핌버를 진행한다. 각 사람의 턴이 되면, 돌 더미 하나를 선택해 돌을 제거한다. 제거한 돌의 개수는 피보나치 수여야 한다.</p> <p>전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. </p> <p>게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.</p> ## 입력 <p>첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 10⁵)이 주어진다. 둘째 줄에 각 돌 더미에 쌓여있는 돌의 개수 P_i (1 ≤ P_i ≤ 3×10⁶)가 주어진다.</p> ## 출력 <p>koosaga가 이기는 경우에는 "koosaga"를, cubelover가 이기는 경우에는 "cubelover"를 출력한다.</p> ## 풀이 한번의 전처리 과정을 통해 그런디수가 최대 15까지 등장한다는 것을 안 후 모든 그런디수를 빠르게 구한 후 XOR 해주었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 3'000'001; int g[MAX]; bool grundies[16]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> factNum; int a=0, b=1; while(a+b<MAX) { int n = a+b; a = b; b = n; factNum.push_back(n); } for(int i=1;i<MAX;i++) { memset(grundies, 0, sizeof grundies); for(int e : factNum) { if(e>i) break; grundies[g[i-e]]=true; } for(int j=0;;j++) { if(!grundies[j]) { g[i]=j; break; } } } int ret=0; while(n--) { int p; cin >> p; ret ^= g[p]; } cout << (ret ? "koosaga" : "cubelover"); } ```