다각형 게임

• 여러개의 게임을 동시에 진행하는 형태가 아닌것 같아 보이지만, 선을 긋는 행위를 두개의 다각형으로 나누는 것으로 생각할수 있다. 그래서 스프라그-그런디 정리를 적용할수 있는 문제가 된다.
• n각형에 선을 그으면, 선 끝에 해당하는 두개의 꼭지점에서는 더이상 선을 그릴수 없으니까, 결국 i각형과 (n-i-2)각형으로 분리되는 것과 동일하다. g(n) = mex_i{g(i)^g(n-i-2)} 의 식으로 정리할수 있는데, 이렇게 구해지는 g값을 나열해봐도 특별한 패턴을 찾기는 힘들다. 그냥 DP로 g(0)부터 g(n)까지 차례차례 계산하면 O(n^2)에 g(n)을 구할수 있다.
  • 다른사람의 코드를 보고서 n이 15 또는 35이거나, n%34가 5,9,21,25,29 중 하나일때, g(n)이 0이 된다는 규칙을 알게 되었다. 이 식을 이용하면 O(1)에도 풀리긴 하겠다.. 그러나 어떻게 저렇게 되는지는 전혀 모르겠다
  • 사실 이 게임은 Octal Game 중 Dawson's Kayle 과 동일한 게임이고, 이 게임은 그런디수가 34의 주기를 갖는다는 것이 잘 알려져 있어서, 그 사실을 이용하면 O(1)에 푸는것도 가능하다.
    • Game on Plane도 동일한 게임이고, 여기에서는 그런디수의 주기성을 이용해서 풀었다.

"""Solution code for "BOJ 13034. 다각형 게임".

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

Tags: [Sprague-Grundy]
"""


def main():
    N = int(input())

    grundy = [0] * (N + 1)
    for i in range(2, N + 1):
        next_grundy_nums = {
            grundy[j] ^ grundy[i - j - 2] for j in range(i // 2)
        }
        grundy[i] = next(x for x in range(N) if x not in next_grundy_nums)

    print('1' if grundy[N] > 0 else '2')


if __name__ == '__main__':
    main()