체스 연습

• Wythoff's game인데, 이 게임은 어떤 포지션에서의 승리/패배 여부는 공식으로 계산할수 있지만, 그런디수는 공식이 따로 없다.
• 그래서 DP를 이용해서 그런디수를 계산하면 된다. 포지션의 갯수는 O(x*y)이고, 행동의 갯수는 O(x+y)개이므로, 총 시간복잡도 O(x*y*(x+y))에 구할수 있다.
• '(0,0)에 하나라도 먼저 놓는 사람이 이긴다' 라는 규칙이 조금 헷갈릴수 있다. 바꿔서 생각하면, (0,0)으로 이동할수 있는 포지션인 (0,n), (n,0), (n,n) 으로 이동하면 다음턴에 바로 지기때문에 저 포지션들은 이동불가능 포지션이라고 생각하면 된다. 만약 시작 포지션이 저 포지션이라면 바로 선공의 승리가 된다. 그러면, 패배포지션은 이동가능한 위치가 (0,n), (n,0), (n,n)밖에 없는 포지션이다. (1,2)와 (2,1)이 저기에 해당한다. 이 두 포지션을 그런디수가 0인 최종 포지션으로 두고 x,y를 증가시키면서 dp로 그런디수를 구하면 된다.
• Bolinhas de Gude도 동일한 문제이다

"""Solution code for "BOJ 1542. 체스 연습".

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

Tags: [game theory]
"""

import functools
import operator

INF = float('inf')


def compute_game():
    grundy = [[0] * 100 for _ in range(100)]
    for i in range(100):
        grundy[i][i] = INF
    for r in range(1, 100):
        for c in range(r + 1, 100):
            next_grundy_nums = set()
            for nr in range(1, r):
                next_grundy_nums.add(grundy[nr][c])
            for nc in range(1, c):
                next_grundy_nums.add(grundy[r][nc])
            for nr, nc in zip(range(r - 1, 0, -1), range(c - 1, 0, -1)):
                next_grundy_nums.add(grundy[nr][nc])
            grundy[r][c] = grundy[c][r] = next(
                i for i in range(300) if i not in next_grundy_nums
            )
    return grundy


def main():
    grundy = compute_game()
    for _ in range(5):
        N = int(input())
        X_and_Y = [[int(x) for x in input().split()] for _ in range(N)]

        if any(x == y or x == 0 or y == 0 for x, y in X_and_Y):
            print('S')
            continue

        tot_grundy = functools.reduce(
            operator.xor, (grundy[x][y] for x, y in X_and_Y)
        )
        print('S' if tot_grundy > 0 else 'D')


if __name__ == '__main__':
    main()