P7027: 圆形谷仓

---

【题目描述】

【题目描述】
Farmer John 和他的死对头 Farmer Nhoj 在一个环形牛棚内玩游戏。牛棚内有 N（1≤N≤10^5）个房间，第 i 个房间初始时内有 ai 头奶牛（1≤ai≤5×10^6）。游戏玩法如下：
1.两位农夫将总是在同一个房间里。进入一个房间后，每位农夫各执行一次行动，Farmer John 在先。两位农夫在游戏开始时进入房间 1。
2.如果当前房间中的奶牛数量为零，则此时执行行动的农夫即失败。否则，执行行动的农夫选择一个整数 P，其中 P 为 1 或一个不超过当前房间中奶牛的数量的质数，并从当前房间中移除 P 头奶牛。
3.两位农夫均完成行动之后，两位农夫移动到环形牛棚的下一间房间。也就是说，如果农夫们在房间 i，那么他们会移动到房间 i+1，除非他们在房间 N，在这种情况下他们会移动到房间 1。
当两位农夫均采用最优策略时，求获胜的农夫。
【输入格式】（从终端 / 标准输入读入）：
输入包含 T 个子测试用例。输入的第一行包含 T（1≤T≤1000）。下面是 T 个子测试用例。
每个子测试用例的第一行包含 N，第二行包含 a1,…,aN。
输入保证所有 N 之和不超过 2×10^5。
【输出格式】（输出至终端 / 标准输出）：
对于每一个子测试用例，输出获胜的农夫，为 "Farmer John" 或 "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
【样例说明】
对于第一个子测试用例，Farmer John 可以从第一个房间中移除 1、2 或 3 头奶牛。无论他移除多少头奶牛，Nhoj 都可以移除剩余的奶牛，迫使 FJ 在他们绕回第一个房间时失败。
对于第二个子测试用例，FJ 可以移除 5 头奶牛，迫使 Nhoj 面对剩下的 4 头奶牛。现在，Nhoj 可以移除 1、2 或 3 奶牛。现在的情况类似于第一个子测试用例。
对于第三个和第四个子测试用例，FJ 可以立即移除第一个房间的所有奶牛，使 Nhoj 失败。
对于第五个子测试用例，FJ 可以从第一个房间中移除 1、2 或 3 奶牛，然后 Nhoj 可以随后移除余下的奶牛。当他们绕回第一个房间时，FJ 将会失败。
【测试点性质】：
测试点 2-4 满足 N=1。
测试点 1，2，5-7 满足 ai≤1000。
测试点 8-20 没有额外限制。
 

题目类型~

USACO-2022-银-12 

咻咻~

提交答案 状态 返回