hdu 1907 John (anti—Nim)

时间:2022-08-31 13:53:47

John

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
http://acm.hdu.edu.cn/showproblem.php?pid=1907

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
2
3
3 5 1
1
1
 
Sample Output
John
Brother
 
题意:Nim取石子,取到最后一个的输
若局面异或和为不为0,定义其为S态,否则,定义其为T态
若一堆石子只有1个,定义其为孤独堆,否则,定义其为充裕堆
 
S0:无充裕堆,异或和不为0
S1:有1个充裕堆,异或和不为0
S2:有>=2个充裕堆,异或和不为0
T0:无充裕堆,异或和为0
T1不存在
T2:有>=2个充裕堆,异或和为0
 
S0:一定是有奇数个孤独堆,所以必败
T0:一定是有偶数个孤独堆,必胜
S1:若孤独堆个数为奇数,则拿空充裕堆,那么留给对方的是S0态,所以S1必胜
S2:可以转到S1、T2
T2:可以转到S1、S2
若T2转到了S2,则S2有转回了T2
若T2转到了S1,则T2必败
所以S2必胜
 
#include<cstdio>
using namespace std;
int main()
{
int T,n,x,sum,yh;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
sum=yh=;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
yh^=x;
if(x>) sum++;
}
if(yh&&!sum) printf("Brother\n");
else if(!yh&&sum>=) printf("Brother\n");
else printf("John\n");
}
}
 

hdu 1907 John (anti—Nim)的更多相关文章

  1. hdu 1907 John(anti nim)

    John Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submis ...

  2. HDU 1907 John (Nim博弈)

    John Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submis ...

  3. POJ 3480 &amp&semi;amp&semi; HDU 1907 John(尼姆博弈变形)

    题目链接: PKU:http://poj.org/problem? id=3480 HDU:http://acm.hdu.edu.cn/showproblem.php? pid=1907 Descri ...

  4. HDU 1907 John(博弈)

    题目 参考了博客:http://blog.csdn.net/akof1314/article/details/4447709 //0 1 -2 //1 1 -1 //0 2 -1 //1 2 -1 / ...

  5. HDU 1907 John(取火柴博弈2)

    传送门 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int ...

  6. hdu 2509 Be the Winner(anti nim)

    Be the Winner Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tot ...

  7. HDU 5795 A Simple Nim(简单Nim)

    p.MsoNormal { margin: 0pt; margin-bottom: .0001pt; text-align: justify; font-family: Calibri; font-s ...

  8. HDU 3533 Escape(大逃亡)

    HDU 3533 Escape(大逃亡) /K (Java/Others)   Problem Description - 题目描述 The students of the HEU are maneu ...

  9. HDU 1043 Eight(八数码)

    HDU 1043 Eight(八数码) 00 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)   Problem Descr ...

随机推荐

  1. TODO:Go语言同名Go字体发布

    TODO:Go语言同名Go字体发布 2016-11-16 Go语言官方博客发布了一款同名字体–Go字体.此字体族包括正常.粗体和斜体渲染,支持比例和等宽字体.此字体已经经过用于编程方面的技术测试,使用 ...

  2. WebViewJavascriptBridge详细使用(转载)

    WebViewJavascriptBridge是支持到iOS6之前的版本的,用于支持native的iOS与javascript交互.如果需要支持到iOS6之前的app,使用它是很不错的.本篇讲讲Web ...

  3. error C2065&colon; &OpenCurlyDoubleQuote;CMainFrame”&colon; 未声明的标识符

    xxxView.cp的开头包含 框架的头文件即可 : #include "MainFrm.h"

  4. Apache2&period;2 &plus; php-5&period;4&period;45-Win32-VC9-x86 配置

    首先要注意一个问题是:网上有很多教程比如: 在Apache配置文件中添加php模块.在apache2\conf\httpd.conf中: LoadModule模块添加行: LoadModule php ...

  5. I&period;MX6 show battery states in commandLine

    #/bin/sh # I.MX6 show battery states in commandLine # 声明: # 在命令行下自动显示电池状态的信息. # # -- # set battery r ...

  6. 打造强势智能手表平台&colon;Testin云測携手索尼招募全球开发人员

    打造强势智能手表平台:Testin云測携手索尼招募全球开发人员 2014/10/27 · Testin · 业界资讯 日前,全球最大的移动游戏.应用真机和用户云測试平台Testin云測宣布联手索尼公司 ...

  7. AES - Rijndael 算法&lpar;三&rpar;

    四.Rijndael算法实现,java版本 public class Rijndael_Algorithms {  private byte[] key;  /**------------------ ...

  8. flask中的session&comma;render&lowbar;template&lpar;&rpar;第二和参数是字典

    1. 设置一个secret_key 2.验证登入后加上session,这是最简单,不保险 . 3.注意render_template传的参数是字典

  9. 如何上传本地项目到gitHub解决方案

    最近有人有人问到我怎么将新创建的本地代码上传到github上,这里简单的记录一下,我喜欢使用命令行,这里全用命令行来实现,不了解Git命令的可以去了解下. 1.  建立本地仓库,cd到你想要上传文件的 ...

  10. flask 搭建ssl接口

    from flask import Flask,jsonifyapp = Flask(__name__)#app.config['SERVER_NAME'] = 'example.com' @app. ...