#P5944. [Usaco2022 Dec]Circular Barn S

    ID: 4944 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高博弈论必胜/必败状态递推数论线性筛排序与序列处理前后缀最值CF2200

[Usaco2022 Dec]Circular Barn S

题目描述

Farmer John 和 Farmer Nhoj 在一座环形谷仓里玩游戏。谷仓有 NN 个房间,第 ii 个房间最初有 aia_i 头牛。两人始终在同一间,最初都进入房间 11。

每次进入一间房,两人各行动一次,Farmer John 先手。当轮到某人行动时,若房间里没有牛,他立即输掉游戏。否则,他选一个不超过房间当前牛数的正整数 PP,移走 PP 头牛。PP 必须为 11 或质数。

两人都行动后一起进入下一间房,从房间 ii 进入 i+1i+1,从房间 NN 回到房间 11。求双方都采用最优策略时的胜者。

输入格式

第一行一个整数 TT(1≤T≤10001\le T\le1000),表示数据组数。

每组数据第一行一个整数 NN(1≤N≤1051\le N\le10^5),第二行 NN 个整数 a1,…,aNa_1,\ldots,a_N(1≤ai≤5×1061\le a_i\le5\times10^6)。所有数据组的 NN 之和不超过 2×1052\times10^5。

输出格式

每组数据输出一行,写出胜者 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

第 11 组中,John 移走 11、22 或 33 头后,Nhoj 可以移走剩下的牛。下次回到第一间时 John 输。第 22 组中,John 可以先移走 55 头,留 44 头给 Nhoj,此后与第 11 组的情况对调。第 33、44 组中,John 可以立即移走第一间的所有牛,令 Nhoj 输。第 55 组中,John 在第一间只能移走 11、22 或 33 头,Nhoj 可移走剩余的牛,并在回到第一间时获胜。

测试点性质

  • 测试点 2–4 满足 N=1N=1。
  • 测试点 1、2、5–7 满足 ai≤1000a_i\le1000。
  • 测试点 8–20 无额外限制。