====== Game on Plane ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

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