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()