룩, 비숍, 킹, 나이트, 궁전 게임

• 궁전 게임의 확장 문제. 똑같이 스프라그-그런디 정리에 기반해서, 각 피스에 대해 그런디 수를 구하고 모두 xor해서 전체 상태에 대한 그런디수를 구해주면 된다.
• 다만 궁전 게임 에서 궁전이 x,y 좌표에 있을때에 그런디 수를 바로 계산할수 있는 공식을 찾았던것 처럼, 룩, 비숍, 킹, 나이트에 대해서도 똑같이 공식을 찾아줘야 한다. 다행히 궁전보다는 쉽다.
• 룩은 간단하다. x좌표가 줄어들거나 y좌표가 줄어들거나 둘중 하나인데, 두 무더기를 갖고 하는 님게임과 동일하다. 그냥 x^y가 그런디 수가 된다
• 비숍도 간단하다. 비숍은 4방향의 대각선으로 움직일수 있지만, 문제 조건에 맞게 움직이려면 한방향만 가능하다. 움직일수 있는 범위는 1~min(x,y) 이고, 그런디수는 그대로 min(x,y) 이다
• 킹은 패턴을 좀 그려볼 필요가 있다.

  • . . . . . . . .   . 
    . . . . . . . . .
    1 2 1 2 1 2 3 2 . .
    0 3 0 3 0 1 0 1 . .
    1 2 1 2 3 2 3 2 . .
    0 3 0 1 0 1 0 1 . .
    1 2 3 2 3 2 3 2 . .
    0 1 0 1 0 1 0 1 . .

  • (x,y)의 그런디값이 (x-2, y-2)의 그런디 값과 같다.
  • 패턴을 최대한 간명하게 식으로 옮겨보면 abs(x - y) % 2 + min(x, y) % 2 * 2 이 된다
• 나이트도 패턴을 좀 그려봐야 한다

  • . . . . . . . .   . 
    . . . . . . . . .
    0 1 2 0 1 1 2 2 . .
    0 1 2 0 0 1 1 1 . .
    0 1 1 0 0 0 0 0 . .
    0 1 1 1 2 2 2 2 . .
    0 0 1 1 1 1 1 1 . .
    0 0 0 0 0 0 0 0 . .

  • (x,y)의 그런디값이 (x-3, y-3)의 그런디 값과 같다.
  • 패턴을 최대한 간명하게 식으로 옮겨보면 m = min(x, y) % 3 으로 두었을때, 그런디값은 abs(x - y) < m 이면 m-1, 그렇지 않으면 m이 된다
• 이제 어떤 피스든지 O(1)에 그런디 수를 계산할수 있다. n개에 피스에 대해서 그런디 수를 구하고 전체 보드 상태에 대한 그런디 수를 구하는 것 까지 O(n)에 처리된다.

"""Solution code for "BOJ 16880. 룩, 비숍, 킹, 나이트, 궁전 게임".

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

Tags: [Sprague-Grundy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    grundy_num = 0
    for _ in range(N):
        x, y, c = sys.stdin.readline().split()
        x, y = int(x), int(y)
        if c == 'R':
            grundy = x ^ y
        elif c == 'B':
            grundy = min(x, y)
        elif c == 'K':
            grundy = abs(x - y) % 2 + min(x, y) % 2 * 2
        elif c == 'N':
            m = min(x, y) % 3
            grundy = (m - 1) if abs(x - y) < m else m
        elif c == 'P':
            grundy = ((x // 3) ^ (y // 3)) * 3 + (x + y) % 3
        grundy_num ^= grundy

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


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.linear_homogeneous_recurrence