Circular Barn

题目描述

农夫 John 和他的宿敌农夫 Nhoj 正在一个圆形牛棚里玩游戏。牛棚中有 $N$ 个房间（$1 \leq N \leq 10^5$），第 $i$ 个房间初始有 $a_i$ 头牛（$1 \leq a_i \leq 5\cdot 10^6$）。游戏规则如下： 两位农夫始终在同一个房间里。进入一个房间后，两位农夫各进行恰好一次操作，且农夫 John 先手。两位农夫最开始进入 1 号房间。 如果当前房间里牛的数量为 0，那么轮到操作的那位农夫失败。 否则，轮到操作的农夫选择一个整数 $P$，其中 $P$ 必须为 $1$ 或者不超过当前房间牛数的某个质数，然后从当前房间移除 $P$ 头牛。 当两位农夫都完成操作后，他们一起移动到圆形牛棚的下一个房间。也就是说，如果他们在房间 $i$，则移动到房间 $i+1$；若他们在房间 $N$，则移动到房间 $1$。 在双方都采取最优策略的情况下，判断最终哪位农夫获胜。

输入格式

输入包含 $T$ 组测试用例。第一行是 $T$（$1 \leq T \leq 1000$）。接下来是 $T$ 组测试用例。 每组测试用例第一行是 $N$，第二行包含 $a_1,\dots,a_N$。 保证所有测试用例的 $N$ 之和不超过 $2\cdot 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

提示

对于第一组样例，农夫 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 满足 $a_i\le 1000$。 输入 8-20 无额外限制。 题目致谢：Chongtian Ma, Jesse Choe, and Yuval Vaknin

标签: USACO|2022|Silver

来源

USACO|2022|Silver