목차

핌버

ps
링크acmicpc.net/…
출처BOJ
문제 번호16877
문제명핌버
레벨플래티넘 3
분류

스프라그-그런디 정리

시간복잡도O(m+nlogn)
인풋사이즈m<=10^5, n<=3*10^6
사용한 언어Python
제출기록62224KB / 3244ms
최고기록3244ms
해결날짜2022/06/08

풀이

코드

"""Solution code for "BOJ 16877. 핌버".

- Problem link: https://www.acmicpc.net/problem/16877
- Solution link: http://www.teferi.net/ps/problems/boj/16877

Tags: [Sprague-Grundy]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    P = [int(x) for x in input().split()]

    max_p = max(P)
    fibo_nums = [2, 3]
    while fibo_nums[-1] < max_p * 2:
        fibo_nums.append(fibo_nums[-1] + fibo_nums[-2])

    grundy = [0b1]
    fibo_index = []
    while (i := len(grundy)) <= max_p:
        while i >= fibo_nums[0]:
            fibo_index.append(-fibo_nums.pop(0))
        next_grundy_nums = grundy[-1]
        for ind in fibo_index:
            next_grundy_nums |= grundy[ind]
        x = ~next_grundy_nums
        grundy_i = (x & -x)
        grundy.append(grundy_i)
        # If grundy[i] is 0, grundy[i+1:i+4] is [1,2,3].
        if grundy_i == 0b1:
            grundy.append(0b10)
            grundy.append(0b100)
            grundy.append(0b1000)

    grundy_num = 0
    for p_i in P:
        grundy_num ^= (grundy[p_i].bit_length() - 1)

    print('koosaga' if grundy_num > 0 else 'cubelover')


if __name__ == '__main__':
    main()