Circular Barn

• 헛간 하나만 놓고 생각하자.
• 제거할수 있는 갯수가 1,2,3개뿐이라면, 배스킨라빈스와 같은 논리로 4의 배수일때는 패배포지션, 나머지는 승리 포지션이 된다.
• 이 외에도 P개만큼 제거하는것도 가능하지만, P는 소수이고 그래서 4의 배수가 될수 없으므로, P개만큼 제거하는 액션을 취한다고 해도, 기존 패배포지션에서 승리포지션으로 이동하는 것은 불가능하다. 따라서 승리/패배 포지션에는 영향을 미치지 못한다. 여전히 4의 배수는 패배포지션, 나머지는 승리포지션이다.
• 이렇게 헛간 하나에 대해서 선공과 후공중 누가 승리하는지를 구하는 것은 간단하다.
• 하지만 이 문제에서는 여러개의 헛간을 돌아가면서 플레이한다. 그리고 승리/패배는 가장 짧은 턴에 승패가 결정되는 헛간의 게임결과에 따라서 정해진다. 이것을 처리하기 위해서는, 각 헛간에서 누가 승리하는지 뿐 아니라, 누가 최소 몇턴만에 승리하는지를 구해야 한다.
• 한번 헛간에 들어가서 선공과 후공이 한번씩 액션을 취하는 것을 1턴이라고 하자. 소가 마리수가 소수개라면, 선공은 1턴만에 이길수 있다. 소의 마리수가 소수+4라면, 선공은 소수개를 제거해서 후공한테 4를 넘겨주고, 후공이 1,2,3중 몇개를 제거하든 다음턴에 0개로 만들수 있다. 따라서 2턴만에 승리할수 있다. 마찬가지로, 소수+8이라면 3턴, 소수+12라면 4턴만에 승리한다.
• 후공은 소가 4k마리 있을때 승리할수 있다. 소가 4마리라면 2턴이 걸리고, 소가 8마리라면 3턴, 12마리라면 4턴이 걸려서 승리한다.
• 이걸 합치면, 소가 n마리 있을때의 턴수 turn[n] 은, n이 0이나 소수이면 1, n이 소수가 아니면 turn[n-4]+1 로 계산할수 있다.
• O(nloglogn)에 소수 목록을 구하고, O(n)에 turn 테이블을 모두 채워놓으면, m개의 헛간이 주어진 케이스에서의 승자를 O(m)에 구할수 있다.

"""Solution code for "BOJ 26973. Circular Barn".

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

Tags: [game theory]
"""

import sys
from teflib import numtheory


def main():
    T = int(sys.stdin.readline())
    a_list = []
    for _ in range(T):
        N = int(sys.stdin.readline())  # pylint: disable=unused-variable
        a = [int(x) for x in sys.stdin.readline().split()]
        a_list.append(a)

    max_a = max(max(a) for a in a_list)
    turn_count = [None] * (max_a + 1)
    turn_count[0] = 1
    turn_count[1] = 1
    for p in numtheory.prime_list(max_a):
        turn_count[p] = 1
    for t in range(3, max_a + 1):
        if turn_count[t] is None:
            turn_count[t] = turn_count[t - 4] + 1

    for a in a_list:
        argmin_a = min(a, key=turn_count.__getitem__)
        print('Farmer John' if argmin_a % 4 != 0 else 'Farmer Nhoj')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list