궁전 게임

• 궁전들이 겹쳐도 상관 없기때문에, 궁전이 한개만 올라가있는 체스판 N개가 독립적으로 있는 상황으로 생각해도 된다. 그러면 스프라그-그런디 정리를 이용해서 궁전 위치에 따른 그런디 수를 구한 다음에 모두 xor해주면 끝.
• 좌표에 따른 그런디 수를 구하는 것은, 쉽게 패턴이 떠오르지는 않는다. 한참 일일히 계산해서 그려보다보면 아래와 같은 패턴이 보인다

  • . . . . . .  .  .  .  .
    . . . . . .  .  .  . .
    5 3 4 2 0 1 11  9 10 ...
    4 5 3 1 2 0 10 11  9 ...
    3 4 5 0 1 2  9 10 11 ...
    2 0 1 5 3 4  8  6  7 ...
    1 2 0 4 5 3  7  8  6 ...
    0 1 2 3 4 5  6  7  8 ...

• 3*3칸 단위로 끊어보면 이런 패턴이고..

  • x+2   x   x
    x+1 x+2   x
    x   x+1 x+2

• 3*3칸 단위로 묶어서 x/3 값만 적어보면 아래처럼 2^k *2^k 단위로 다시 패턴이 반복된다

  • . . . . . . . .
    3 2 1 0 7 6 5 4 ...
    2 3 0 1 6 7 4 5 ...
    1 0 3 2 5 4 7 6 ...
    0 1 2 3 4 5 6 7 ...

• 이제 이 패턴을 이용해서 grundy 수를 구하면 된다. 대충 O(log(n)) 정도의 시간복잡도로 구현했는데.. 구현이 좀 복잡하긴 했다.
  • 제출후 다른사람의 코드를 보고 나니, 아래 패턴은 그냥 x^y 로 계산되는 값이라는 것을 알게 되었다..; 구현하느라 엄청 삽질했는데 허무함.. 아무튼 이렇게 좌표 (x,y)의 그런디수는 ((x/3)^(y/3))*3+(x+y)%3 으로 O(1)에 계산 가능하다. N개의 말에 대해 각각 그런디수를 계산해서 xor하는것은 총 O(N)이 걸린다.

"""Solution code for "BOJ 16879. 궁전 게임".

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

Tags: [Sprague-Grundy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    grundy_num = 0
    for _ in range(N):
        x, y = [int(x) for x in sys.stdin.readline().split()]
        grundy_num ^= ((x // 3) ^ (y // 3)) * 3 + (x + y) % 3
    print('koosaga' if grundy_num else 'cubelover')


if __name__ == '__main__':
    main()