HDu 1907 John(マッチ取りゲーム)
3184 ワード
ニムゲーム(Nimm Game):3つの山にそれぞれいくつかのものがあり、2人は交代である山から任意の多くのものを取り、毎回少なくとも1つを取ることを規定している.
(a,b,c)である情勢を表すと、まず(0,0,0)は明らかに奇異な情勢(すなわち、後に人が必ず物を取る)であり、第2の奇異な情勢は(0,n,n)であり、相手と同じように多くのものを持っていくと、最後に(0,0,0)になる.3つ目の(1,2,3)も奇異な情勢で、相手がどう取っても、次は(0,n,n)になる場合があります.
(+)で異或(ビットモード2加算とも呼ばれる)演算を表し、いかなる奇異な情勢に対してもa 1(+)a 2(+)......(+)an=0である.
マッチを取るゲームのテーマ1:今いくつかのマッチがあって、2人は順番に中から取って、毎回1つの山の中からいくつかの根を取ることしかできなくて、1つの山を全部取ることができて、しかし取らないことができなくて、最後に取った者は勝って、必ず勝つ方法を求めます.
タイトル2:今いくつかのマッチの山があって、2人は顺次中から取って、毎回1山の中からいくつかの根を取ることしかできなくて、1山を全部取ることができて、しかし取らないことができなくて、最后に取り终わった者は负で、必ず胜つ方法を求めます.
定義:すべてのマッチの数が0である場合、この状態は利他状態と呼ばれ、アルファベットTで表される.さもなくば、利己的な状態のため、Sで表します.
[定理1]:いずれのS状態に対しても、マッチの山からいくつか取り出してT状態にすることができる.
[定理2]:T状態は,どの山のいくつかの根を取ってもS状態になる.
[定理3]:S状態は,方法が正しい限り,必ず勝つ.
[定理4]:T状態は,方法が正しい限り,必ず負ける.
次に2つ目の問題を解決します.定義:マッチが1本しかない場合は、孤独な山と呼ばれます.1本より大きい場合は、余裕スタックと呼ぶ.定義:T状態で、余裕スタックのスタック数が2以上であれば(余裕スタック数が1であれば、最後には0ではなく、高位が1つしかないため、異または結果は0ではない)、完全利他状態と呼ばれ、T 2で表される;余裕スタックのスタック数が0であれば、部分利他状態と呼ばれ、T 0で表される(孤独な山の数は必ず偶数であることを説明します.そうしないと、異や結果は0ではありません.偶数なので、後で持っているものは必ず最後にすべてのものを取ります.2番目の問題で先に持っているのは勝者です).
孤单堆の根数異はバイナリの最後の1位にしか影響しないが、余裕堆は高位(非最後の1位)に影響する.1つの余裕堆は、高位が必ず1位が0でなければ、すべての根数異は0ではない.だからT状態ではない.
[定理5]:S 0状態、すなわち奇数個の孤独な山しかなく、必ず負ける.T 0態必勝.
[定理6]:S 1状態(余裕のある山、x個の孤独な山)、方法が正しい限り、必ず勝つ.
証明:この時、孤独なスタック数が奇数であれば、余裕のあるスタックを取り終え、S 0になる.
そうでなければ偶数個の孤独な山があり、余裕の山を1本残します.これにより、奇数個の孤独な山であるS 0になり、相手が取る.
定理5から、必ず勝つ.
[定理7]:S 2状態を一度にT 0状態に変えることはできない.
[定理8]:S 2状態はT 2状態に一度に遷移することができる.
(余裕スタック>2(1:余裕スタックが偶数で、孤独スタックが奇数で、1つの孤独スタックを取り終える),(2:余裕スタックが奇数で、孤独スタックが偶数であれば、1つの余裕スタックを取り終え、孤独スタックが奇数であれば、1つの余裕スタックを1つ残す)
[定理9]:T 2状態は,S 2状態またはS 1状態にしか遷移できない.(余裕スタック>2であればS 2に、余裕スタック=2であればS 1に変換することができる).
[定理10]:S 2状態、方法が正しい限り、必ず勝つ.
証明:方法は以下の通りである:1)S 2状態(①)をT 2状態(②)に変える.(定理8)2)相手はT 2からS 2状態またはS 1状態(①)(定理9)をS 2に変えると、1)をS 1(①)に変えると、必ず勝つ.(定理5)
定理11]:T 2状態は必ず負ける.
以上、S 2,S 1,T 0であれば.先の者は必ず勝つ.
T 2ならS 0.先の人は必ず負ける.
2つの問題の比較:
第1題(全過程):S 2->T 2->S 2->T 2->T 2->T 2->T 2->T 2->T 2->T 2->T 0(全0)
第2題(全過程):S 2->T 2->S 2->T 2->……->T 2->S 1->S 0(技術個孤单堆)->T 0->S 0->…->S 0->T 0(全0)
S 1の状態はS 0の状態(第2の問題のやり方)に変えることができて、T 0(第1の問題のやり方)に変えることができます.どちらがS 1の状態を制御して、彼は自分を最後の1本(T 0に変える)を得ることができて、相手に最後の1本を得ることができます(S 0に移行).だから、S 1を奪うことが勝負の鍵!そのため、T 2状態を常に相手に譲り、相手を受動状態にし、遅かれ早かれS 1状態に変える.
コード:
(a,b,c)である情勢を表すと、まず(0,0,0)は明らかに奇異な情勢(すなわち、後に人が必ず物を取る)であり、第2の奇異な情勢は(0,n,n)であり、相手と同じように多くのものを持っていくと、最後に(0,0,0)になる.3つ目の(1,2,3)も奇異な情勢で、相手がどう取っても、次は(0,n,n)になる場合があります.
(+)で異或(ビットモード2加算とも呼ばれる)演算を表し、いかなる奇異な情勢に対してもa 1(+)a 2(+)......(+)an=0である.
マッチを取るゲームのテーマ1:今いくつかのマッチがあって、2人は順番に中から取って、毎回1つの山の中からいくつかの根を取ることしかできなくて、1つの山を全部取ることができて、しかし取らないことができなくて、最後に取った者は勝って、必ず勝つ方法を求めます.
タイトル2:今いくつかのマッチの山があって、2人は顺次中から取って、毎回1山の中からいくつかの根を取ることしかできなくて、1山を全部取ることができて、しかし取らないことができなくて、最后に取り终わった者は负で、必ず胜つ方法を求めます.
定義:すべてのマッチの数が0である場合、この状態は利他状態と呼ばれ、アルファベットTで表される.さもなくば、利己的な状態のため、Sで表します.
[定理1]:いずれのS状態に対しても、マッチの山からいくつか取り出してT状態にすることができる.
[定理2]:T状態は,どの山のいくつかの根を取ってもS状態になる.
[定理3]:S状態は,方法が正しい限り,必ず勝つ.
[定理4]:T状態は,方法が正しい限り,必ず負ける.
次に2つ目の問題を解決します.定義:マッチが1本しかない場合は、孤独な山と呼ばれます.1本より大きい場合は、余裕スタックと呼ぶ.定義:T状態で、余裕スタックのスタック数が2以上であれば(余裕スタック数が1であれば、最後には0ではなく、高位が1つしかないため、異または結果は0ではない)、完全利他状態と呼ばれ、T 2で表される;余裕スタックのスタック数が0であれば、部分利他状態と呼ばれ、T 0で表される(孤独な山の数は必ず偶数であることを説明します.そうしないと、異や結果は0ではありません.偶数なので、後で持っているものは必ず最後にすべてのものを取ります.2番目の問題で先に持っているのは勝者です).
孤单堆の根数異はバイナリの最後の1位にしか影響しないが、余裕堆は高位(非最後の1位)に影響する.1つの余裕堆は、高位が必ず1位が0でなければ、すべての根数異は0ではない.だからT状態ではない.
[定理5]:S 0状態、すなわち奇数個の孤独な山しかなく、必ず負ける.T 0態必勝.
[定理6]:S 1状態(余裕のある山、x個の孤独な山)、方法が正しい限り、必ず勝つ.
証明:この時、孤独なスタック数が奇数であれば、余裕のあるスタックを取り終え、S 0になる.
そうでなければ偶数個の孤独な山があり、余裕の山を1本残します.これにより、奇数個の孤独な山であるS 0になり、相手が取る.
定理5から、必ず勝つ.
[定理7]:S 2状態を一度にT 0状態に変えることはできない.
[定理8]:S 2状態はT 2状態に一度に遷移することができる.
(余裕スタック>2(1:余裕スタックが偶数で、孤独スタックが奇数で、1つの孤独スタックを取り終える),(2:余裕スタックが奇数で、孤独スタックが偶数であれば、1つの余裕スタックを取り終え、孤独スタックが奇数であれば、1つの余裕スタックを1つ残す)
[定理9]:T 2状態は,S 2状態またはS 1状態にしか遷移できない.(余裕スタック>2であればS 2に、余裕スタック=2であればS 1に変換することができる).
[定理10]:S 2状態、方法が正しい限り、必ず勝つ.
証明:方法は以下の通りである:1)S 2状態(①)をT 2状態(②)に変える.(定理8)2)相手はT 2からS 2状態またはS 1状態(①)(定理9)をS 2に変えると、1)をS 1(①)に変えると、必ず勝つ.(定理5)
定理11]:T 2状態は必ず負ける.
以上、S 2,S 1,T 0であれば.先の者は必ず勝つ.
T 2ならS 0.先の人は必ず負ける.
2つの問題の比較:
第1題(全過程):S 2->T 2->S 2->T 2->T 2->T 2->T 2->T 2->T 2->T 2->T 0(全0)
第2題(全過程):S 2->T 2->S 2->T 2->……->T 2->S 1->S 0(技術個孤单堆)->T 0->S 0->…->S 0->T 0(全0)
S 1の状態はS 0の状態(第2の問題のやり方)に変えることができて、T 0(第1の問題のやり方)に変えることができます.どちらがS 1の状態を制御して、彼は自分を最後の1本(T 0に変える)を得ることができて、相手に最後の1本を得ることができます(S 0に移行).だから、S 1を奪うことが勝負の鍵!そのため、T 2状態を常に相手に譲り、相手を受動状態にし、遅かれ早かれS 1状態に変える.
コード:
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int t , a[50] ,n;
int sum1, sum2 ,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum1=sum2=ans=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]>=2) sum1++;
else sum2++;
ans^=a[i];
}
if(ans!=0 && sum1!=0 || ans==0 && sum1==0)
printf("John
"); // S2, S1（ ）
else if(ans==0 && sum1>=2 || ans!=0 && sum2%2!=0 && sum1==0)
printf("Brother
");
}
return 0;
}