#P5944. [Usaco2022 Dec]Circular Barn S
[Usaco2022 Dec]Circular Barn S
题目描述
Farmer John 和 Farmer Nhoj 在一座环形谷仓里玩游戏。谷仓有 个房间,第 个房间最初有 头牛。两人始终在同一间,最初都进入房间 。
每次进入一间房,两人各行动一次,Farmer John 先手。当轮到某人行动时,若房间里没有牛,他立即输掉游戏。否则,他选一个不超过房间当前牛数的正整数 ,移走 头牛。 必须为 或质数。
两人都行动后一起进入下一间房,从房间 进入 ,从房间 回到房间 。求双方都采用最优策略时的胜者。
输入格式
第一行一个整数 (),表示数据组数。
每组数据第一行一个整数 (),第二行 个整数 ()。所有数据组的 之和不超过 。
输出格式
每组数据输出一行,写出胜者 Farmer John 或 Farmer Nhoj。
样例 #1
样例输入 #1
5
1
4
1
9
2
2 3
2
7 10
3
4 9 4
样例输出 #1
Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj
样例解释 #1
第 组中,John 移走 、 或 头后,Nhoj 可以移走剩下的牛。下次回到第一间时 John 输。第 组中,John 可以先移走 头,留 头给 Nhoj,此后与第 组的情况对调。第 、 组中,John 可以立即移走第一间的所有牛,令 Nhoj 输。第 组中,John 在第一间只能移走 、 或 头,Nhoj 可移走剩余的牛,并在回到第一间时获胜。
测试点性质
- 测试点 2–4 满足 。
- 测试点 1、2、5–7 满足 。
- 测试点 8–20 无额外限制。