hdu 1907 尼姆博弈

John

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3745 Accepted Submission(s): 2116

Problem Description

Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.

Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.

Input

The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.

Constraints:
1 <= T <= 474,
1 <= N <= 47,
1 <= Ai <= 4747

Output

Output T lines each of them containing information about game winner. Print “John” if John will win the game or “Brother” in other case.

Sample Input

Sample Output

John
Brother

Source

Southeastern Europe 2007

Recommend

lcy | We have carefully selected several similar problems for you: 1913 1908 1914 1915 1909

题意大概是有n种颜色的糖豆，john和他的哥哥轮流吃糖，每次可以选择其中的一种颜色中的若干个，最后谁最后吃完谁就输了

思路：

经典的尼姆博弈问题

对于尼姆博弈，类似于威佐夫博弈，奇异局势与非奇异局势碾转变换，先发者如果面对的奇异局势则输，反之则胜

对于如果判断面对的局势是否为奇异局势，有两种情况需要考虑

1 如果所有项都为1的话，只需要判断奇偶的数量就可以了

2 若不为1的情况，如果所有数的异或值为0，那么就是奇异局势，否则不是奇异局势

代码1a，

可做模板

重试信心-------》-----》

#include<stdio.h>
#include<string.h>
#include<math.h>
int a[100];

int main(){
   int t;
   scanf("%d",&t);
   int n;
   while(t--){
        scanf("%d",&n);
        bool flag=true;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i]!=1)
                flag=false;
        }
        int ans=a[1];
        for(int i=2;i<=n;i++)
            ans=ans^a[i];

            if(flag){
               if(n%2)
                     printf("Brother
");
               else
                 printf("John
");

            }
            else{
        if(ans)
            printf("John
");
        else
            printf("Brother
");
            }

   }
   return 0;
}