【题意】
anti-nim游戏
【输入】
第一行一个t,表示t组数据
每组数据第一行一个n,表示n堆石子
接下来一行n个整数表示n堆石子的个数
【输出】
先手赢打"John",否则打"Brother"
anti-nim游戏
1)所有石子堆的数目都为1:
显然,若有偶数堆石子堆,则必胜,否则必败。
2)如果恰好只有一堆石子数目大于1。
我们可以把这堆石子取完或者取得只剩下1,使得只剩下奇数堆数目为1的石子留给对方,由1),必胜。
3)如果有至少2堆石子的数目大于1。
考虑⊕值:
若⊕值不为0,则按照NimGame走法取石。这样,当对手某次取完石子后,肯定会出现2)的情况,则必胜。
按照NimGame法则取完石子后,必定会给对手留下⊕值为0的局面。因此不可能给对手留下2)的局面(容易证明,2)局面的⊕值肯定不为0),而对手一次最多将一堆石子数大于1的石子堆处理掉。因此2)的情况肯定会出现。
相反,若⊕值为0,则无论如何走都会给对方留下2)或3)的情况,必败。
program poj3480; var max,t,n,i,j,k:longint; begin read(t); while t>0 do begin dec(t); read(n); max:=0; k:=0; for i:=1 to n do begin read(j); if j>max then max:=j; k:=k xor j; end; if ((k<>0)and(max>1))or((k=0)and(max<=1)) then writeln('John') else writeln('Brother'); end; end.