1973: [USACO 2022 December Contest Silver] Problem 2. Circular Barn

文件提交：无需freopen 内存限制：256 MB 时间限制：2.000 S
评测方式：普通裁判 命题人：
提交：1 解决：1

题目描述

Farmer John and his archnemesis Farmer Nhoj are playing a game in a circular barn. There are N (1≤N≤105) rooms in the barn, and the ith room initially contains ai cows (1≤ai≤5⋅106). 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 .
  • If there are zero cows in the current room, then the farmer to go loses. Otherwise, the farmer to go chooses an integer P, where P must either be 1 or a prime number at most the number of cows in the current room, and removes P 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 i, then they move to room i+1, unless they are in room N, in which case they move to room 1.

Determine the farmer that wins the game if both farmers play optimally.

输入

The input contains T test cases. The first line contains T (1≤T≤1000). Each of the T test cases follow.

Each test case starts with a line containing N, followed by a line containing a1,…,aN.

It is guaranteed that the sum of all N is at most 2⋅105.

输出

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

样例输入 

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, , 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 cows, forcing Nhoj to work with only cows remaining. Now, Nhoj can either remove , , 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 
, 
, or 
, 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.

SCORING:

  • Inputs 2-4 satisfy N=1.
  • Inputs 1, 2, and 5-7 satisfy ai≤1000.
  • Inputs 8-20 satisfy no additional constraints.


来源/分类

提交提交记录统计露一手!
codingfuture is powered by HUSTOJ, Theme by SYZOJ