Game on Plane

• 처음에는 문제 이해를 잘못해서 시간을 소비했고, 문제 이해를 한 뒤에도 풀이가 바로 생각 안나서 또 시간을 소비했다. 통과된 이후에 Octal game 이라는 관련 이론에 대해서 공부한 시간은 별개..
• 기존에 그어진 선분과 끝점을 공유하는 선분을 긋는것은 가능하다. 그러나 이렇게 그으면 상대방이 다음턴에 곧바로 삼각형을 완성시켜서 지게 되므로, 그냥 그렇게 긋는 것이 불가능하다고 규칙을 바꿔도 동일한 게임이 된다.
• 이렇게 놓고 생각하면, 점 두개를 골라서 선분을 하나 긋는 것은, 남은 점들을 방금 그은 선분을 기준으로 양쪽에 있는 두 그룹으로 분할하는 것이 된다. 다각형 게임과도 동일한 문제가 된다.
• 다각형 게임 에서 푼 것처럼 그런디 수를 dp로 차근차근 구하면 O(n^2)에 계산이 가능하다. 그렇게 구현한 코드는 링크 참조. 그러나 n의 범위가 최대 1000이었던 다각형 게임과 달리 n의 범위가 5000으로 늘어나서 파이썬으로는 통과가 쉽지 않다 (시간추가 없는 1초 제한). 내가 제출해본 결과는 파이썬으로는 시간초과, pypy로는 200ms가 걸렸다.
• 이 문제를 더 빠르게 푸는 방법은, 이 게임에서는 그런디 수가 주기적으로 반복된다는 것을 이용하는 것. 이 게임은 Dawson's Kayles 라는 잘 알려진 게임과 동일한 그런디 수를 갖게 되는 게임이고, Dawson's Kayles의 그런디수는 주기가 34라는 것이 잘 알려져 있다. 자세히는 Octal game 을 참고.
• 이 사실을 이용하면 임의의 n에 대한 그런디 수를 O(1)에 계산할수 있다. T개의 그런디수를 계산하는 데에는 O(T)면 충분하다.

"""Solution code for "BOJ 16187. Game on Plane".

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

Tags: [Sprague-Grundy]
"""

import sys


def is_win_pos_of_dawson_kayles(n):
    return not (n in (15, 35) or n % 34 in (5, 9, 21, 25, 29))


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        print('First' if is_win_pos_of_dawson_kayles(N) else 'Second')


if __name__ == '__main__':
    main()