#PU1255. USACO 2022 December Contest, Silver — Problem 2. Circular Barn

USACO 2022 December Contest, Silver — Problem 2. Circular Barn

USACO 2022 December Contest, Silver — Problem 2. Circular Barn

题目描述

Farmer John and his archnemesis Farmer Nhoj are playing a game in a circular barn. There are NN (1≤N≤1051 \leq N \leq 10^5) rooms in the barn, and the iith room initially contains aia_i cows (1≤ai≤5⋅1061 \leq a_i \leq 5\cdot 10^6). The game is played as follows: Both farmers will always be in the same room. After entering a room, each farmer takes exactly one turn, with Farmer John going first. Both farmers initially enter room 11. If there are zero cows in the current room, then the farmer to go loses. Otherwise, the farmer to go chooses an integer PP, where PP must either be 11 or a prime number at most the number of cows in the current room, and removes PP cows from the current room. After both farmers have taken turns, both farmers move to the next room in the circular barn. That is, if the farmers are in room ii, then they move to room i+1i+1, unless they are in room NN, in which case they move to room 11. Determine the farmer that wins the game if both farmers play optimally.

输入格式

The input contains TT test cases. The first line contains TT (1≤T≤10001 \leq T \leq 1000). Each of the TT test cases follow. Each test case starts with a line containing NN, followed by a line containing a1,…,aNa_1,\dots,a_N. It is guaranteed that the sum of all NN is at most 2⋅1052\cdot 10^5.

输出格式

For each test case, output the farmer that wins the game, either "Farmer John" or "Farmer Nhoj."

数据范围

Inputs 2-4 satisfy N=1N=1. Inputs 1, 2, and 5-7 satisfy ai≤1000a_i\le 1000. Inputs 8-20 satisfy no additional constraints. Problem credits: Chongtian Ma, Jesse Choe, and Yuval Vaknin

样例

样例 1

5
1
4
1
9
2
2 3
2
7 10
3
4 9 4
Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj
For the first test case, Farmer John can remove $1$, $2$, or $3$ cows from  the
first room. Whichever number he removes, Nhoj can remove the remaining cow(s),
forcing FJ to lose when they circle back to the first room.
For the second test case, FJ can remove $5$ cows, forcing Nhoj to work with only
$4$ cows remaining. Now, Nhoj can either remove $1$, $2$, or $3$ cows. This is
now similar to the first test case.
For the third and fourth test cases, FJ can immediately remove all the cows from
the first room, forcing Nhoj to lose.
For the fifth test case, FJ can remove $1$, $2$, or $3$, cows from the first
room, and Nhoj can remove the rest right after. When they circle back around to
the first room, FJ will lose.