NimゲームのHDU 1850 Being a Good Boy in Spring Festival

ニムゲーム(Nimm Game):3つのいくつかの品物があり、2人は交代である山から任意の多くの品物を取り、毎回少なくとも1つを取ることを規定している.
この状況が最も興味深いのはバイナリと密接な関係があります私たちは(a,b,c)である情勢を表し、まず(0,0,0)は明らかに奇異な情勢であり、誰が奇異な情勢に直面しても必ず失敗する.第2の奇異な情勢は(0,n,n)であり、相手と同じように多くのものを持って行けば、最後に(0,0,0)を招く.よく分析してみると、(1,2,3)も奇異な情勢であり,相手がどう取っても次は(0,n,n)の状況になる.
計算機アルゴリズムには、按位模2加という、異或という演算があります.この演算を記号(+)で表します.この演算は一般的な加算とは異なる点で1+1=0です.まず(1,2,3)の按位模2加の結果を見てみましょう.
1=バイナリ012=バイナリ103=バイナリ11(+)—————0=バイナリ00(位置を上げないことに注意)
奇異な情勢(0,n,n)に対しても同様であり,結果も0であった.
いかなる奇異な情勢(a,b,c)にもa(+)b(+)c=0がある.
もし私たちが非特異な情勢(a,b,c)に直面している場合、どのように特異な情勢になるのでしょうか.a例2.(55,81121),55(+)81=102121−102=19であるため,121から19個の物品を持ち出すと奇異な事態となった(55,81102).
例3.(29,45,58),29(+)45=48,58-48=10,58から10個を持ち去り,(29,45,48)となる.
 
 

 1 #include<stdio.h>

 2 int a[110];

 3 int main()

 4 {

 5     int n;

 6     int sum;

 7     while(scanf("%d",&n),n)

 8     {

 9         sum=0;

10         int ans=0;

11         for(int i=0;i<n;i++)

12         {

13             scanf("%d",&a[i]);

14             sum^=a[i];

15         }    

16         for(int i=0;i<n;i++)

17         {

18             if(a[i]>(sum^a[i]))ans++;

19         }    

20         printf("%d
",ans);

21     }    

22     return 0;

23 }