테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 궁전 게임 ======

===== 풀이 =====
  * 궁전들이 겹쳐도 상관 없기때문에, 궁전이 한개만 올라가있는 체스판 N개가 독립적으로 있는 상황으로 생각해도 된다. 그러면 [[ps:스프라그-그런디 정리]]를 이용해서 궁전 위치에 따른 그런디 수를 구한 다음에 모두 xor해주면 끝.
  * 좌표에 따른 그런디 수를 구하는 것은, 쉽게 패턴이 떠오르지는 않는다. 한참 일일히 계산해서 그려보다보면 아래와 같은 패턴이 보인다
    * <code>
. . . . . .  .  .  .  .
. . . . . .  .  .  . .
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 ...
</code>
  * 3*3칸 단위로 끊어보면 이런 패턴이고..
    * <code>
x+2   x   x
x+1 x+2   x
x   x+1 x+2
</code>
  * 3*3칸 단위로 묶어서 x/3 값만 적어보면 아래처럼 2^k *2^k 단위로 다시 패턴이 반복된다
    * <code>
. . . . . . . .
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 ...
</code>
  * 이제 이 패턴을 이용해서 grundy 수를 구하면 된다. 대충 O(log(n)) 정도의 시간복잡도로 구현했는데.. 구현이 좀 복잡하긴 했다.
    * %% 제출후 다른사람의 코드를 보고 나니, 아래 패턴은 그냥 x^y 로 계산되는 값이라는 것을 알게 되었다..; 구현하느라 엄청 삽질했는데 허무함.. 아무튼 이렇게 좌표 (x,y)의 그런디수는 ((x/3)^(y/3))*3+(x+y)%3 으로 O(1)에 계산 가능하다. N개의 말에 대해 각각 그런디수를 계산해서 xor하는것은 총 O(N)이 걸린다. %%
 
===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_1}}