문제 태그

• 게임이론

아이디어

1. 노멀게임임으로 마지막 돌을 가져가는 이가 이김. 기저사례를 0으로 둠
2. 피보나치의 규칙은 없음으로 피보나치를 dp로 구하고 스프라그 그런디수도 dp로 직접 구해야함
3. 돌 무더기 각각을 xor해서 0이면 선공이 이길 수 없음

정답

import sys
input = sys.stdin.readline

M = int(input())
heaps = list(map(int, input().split()))
max_h = max(heaps)

fibs = [1, 2]
while fibs[-1] + fibs[-2] <= max_h:
    fibs.append(fibs[-1] + fibs[-2])

sg = [0] * (max_h + 1)
for i in range(1, max_h + 1):
    seen = set()
    for f in fibs:
        if f > i:
            break
        seen.add(sg[i - f])
    m = 0
    while m in seen:
        m += 1
    sg[i] = m

res = 0
for h in heaps:
    res ^= sg[h]

if res == 0:
    print("cubelover")
else:
    print("koosaga")