与传统的SG游戏不同的是,完成最后一个状态的人是输的,我们把这一类问题称作Anti-SG,这类问题的解决我们需要引入一个定理—SJ定理:
对于任意一个Anti-SG游戏,如果我们规定当局面中所有的单一游戏的SG值为0时,游戏结束,则先手必胜当且仅当:(1)游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1;(2)游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。 (引自2009年国家集训队论文贾志豪论文《组合游戏概述——浅谈SG游戏的若干拓展及变形》)
这样对于这个问题我们就可以很好的解决了:
1、所有堆的石子数都为1且游戏的SG值为0;
2、有些堆的石子数大于1且游戏的SG值不为0。
只有这两种请情况下是先手必胜状态,否则为先手必败状态。
/************************************************************** Problem: 1022 User: BLADEVIL Language: Pascal Result: Accepted Time:40 ms Memory:228 kb ****************************************************************/ //By BLADEVIL var task :longint; i :longint; n :longint; a :array[0..100] of longint; procedure main; var i :longint; ans :longint; f :boolean; begin read(n); ans:=0; for i:=1 to n do read(a[i]); for i:=1 to n do ans:=ans xor a[i]; f:=false; if ans=0 then begin for i:=1 to n do if a[i]<>1 then f:=true; end else for i:=1 to n do if a[i]>1 then f:=true; if (ans=0) and (not f) or (ans<>0) and (f) then writeln(‘John‘) else writeln(‘Brother‘); end; begin read(task); for i:=1 to task do main; end.