算法
(博弈论) $O(N)$
子问题1:判断只有一个房间的情况,先手必胜还是必败?
假设这个房间有 $x$ 头奶牛
结论:当 $x \equiv 0 \pmod 4$ 时,先手必败;否则,先手必胜
当 $x \equiv 0 \pmod 4$ 时, 先手可以移除 4k+1/2/4k+3
头奶牛,相应地,后手可以分别移除 3/2/1
头奶牛
当 $x \equiv 1 /2 / 3 \pmod 4$ 时,先手可以移除 1/2/3/4k+1/4k+3
头奶牛,而后手会面临 $x’ \equiv 0 \pmod 4$ 的状态,此时后手是必败态
子问题2:在哪个房间终结游戏?
这个问题等价于两位农夫都采取最优策略的情况下,每个房间总共需要多少轮次?
单个房间的输赢已经确定,找出 $\{b_i\}$ 的最小值位置,这个位置就是最后游戏终结的房间,并判断这个房间是先手必胜还是先手必败,其中 $b_i = 1 + \lfloor\frac{a_i-p-2}{4}\rfloor + 1 = 1 + \lfloor\frac{a_i-p+2}{4}\rfloor$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
// linear sieve
vector<int> ps, pf, pm, pd; // pm: 和 4 同余的最大素数 pd[i]: 不超过 i 的和 4 同余的最大素数
void sieve(int mx) {
pf.resize(mx+1);
pd.resize(mx+1);
pm.resize(4);
pd[1] = 1;
pm[0] = 2; // 当前情况是 4 的倍数,减去 2 即可,这样是最延缓自己死亡时间的做法
rep(i, mx+1) pf[i] = i;
for (int i = 2; i <= mx; ++i) {
if (pf[i] == i) ps.push_back(i), pm[i%4] = i;
pd[i] = pm[i%4];
for (int j = 0; j < ps.size() and ps[j] <= pf[i]; ++j) {
int x = ps[j] * i;
if (x > mx) break;
pf[x] = ps[j];
}
}
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
auto ok = [&]{
vector<int> b(n);
rep(i, n) b[i] = 1+(a[i]-pd[a[i]]+2)/4;
return a[min_element(b.begin(), b.end()) - b.begin()]%4 != 0;
}();
if (ok) puts("Farmer John");
else puts("Farmer Nhoj");
}
int main() {
sieve(5e6);
int t;
cin >> t;
while (t--) solve();
return 0;
}