POJ 1704：Georgia and Bob

Georgia and Bob

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 9321		Accepted: 3036

Description

Georgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by 1, 2, 3, ..., and place N chessmen on different grids, as shown in the following figure for example:

POJ 1704：Georgia and Bob_i++

Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game.

Georgia always plays first since "Lady first". Suppose that Georgia and Bob both do their best in the game, i.e., if one of them knows a way to win the game, he or she will be able to carry it out.

Given the initial positions of the n chessmen, can you predict who will finally win the game?

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case contains two lines. The first line consists of one integer N (1 <= N <= 1000), indicating the number of chessmen. The second line contains N different integers P1, P2 ... Pn (1 <= Pi <= 10000), which are the initial positions of the n chessmen.

Output

For each test case, prints a single line, "Georgia will win", if Georgia will win the game; "Bob will win", if Bob will win the game; otherwise 'Not sure'.

Sample Input

23 1 2 3 8 1 5 6 7 9 12 14 17

Sample Output

Bob will winGeorgia will win

给一个1*M的棋盘，上面有N颗棋子，每次只能向左移动棋子，并且至少移动一步，两人轮流操作，谁不能移动谁就输了。

很明显的博弈问题，我们可以把整个棋盘中相邻棋子之间的距离计算出来，人为操作可能会使这个距离增大，也可能会让它减小，但是，每两次操作中，不论如何移动棋子，我们都可以假设这个距离一定会减小，这样的话，这个距离就相当于石子的数量，两人轮流取走石子，看谁取走最后的石子啦！问题就这样转换成了Nim博弈，但是如果棋盘上的棋子数量是奇数应该怎么办呢？我们可以添加一个棋子，在棋盘的最左端，也就是它的位置是0，每堆石子的数量可认为是相邻每两个棋子的距离差，然后计算异或，判断数值之后得出结果。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n+10],s=0;
        for(int i=0; i<n; i++)
            cin>>a[i];
        if(n&1)a[n++]=0;
        sort(a,a+n);
        for(int i=1; i<n; i+=2)
            s^=a[i]-a[i-1]-1;
        if(s)cout<<"Georgia will win"<<endl;
        else cout<<"Bob will win"<<endl;
    }
    return 0;
}

查看全文
如若内容造成侵权/违法违规/事实不符，请联系编程学习网邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！

Aha！设计模式(14)-BUILDER(5)
Aha！设计模式(14)-BUILDER(5)，效果这里是Builder模式的主要效果：1)它使你可以改变一个产品的内部表示。首先明确两个词。一是前面已经提到过《设计模式》...
2022/8/10 20:47:38
EA&UML日拱一卒-0基础学习微信小程序(10)-注册页面
EA&UML日拱一卒-0基础学习微信小程序(10)-注册页面，注册过小程序之后，接下来注册页面。代码说明//index.js//获取应用实例varapp=getApp()Page({ data:{ motto:'HelloWorld', userInfo:{} }, //事件处理函数 bindViewTap:func...
2022/8/10 20:47:36
YTU 2907: 类重载实现矩阵加法
YTU 2907: 类重载实现矩阵加法，2907:类重载实现矩阵加法时间限制: 1Sec 内存限制: 128MB提交: 345 解决: 164题目描述编写矩阵类Matrix,实现两个2x3矩阵相加。主函数已给定。输入两个矩阵的元素值输出两个矩阵相加的结果样例输入123456123456样例输出24681012提示...
2022/8/10 20:34:29
Asterisk MWI
Asterisk MWI，MessageWaitingIndication(MWI)<br/>...
2022/8/10 20:34:27
EA&UML日拱一卒-状态图::延缓（处理）事件
EA&UML日拱一卒-状态图::延缓（处理）事件，通过按钮式交通信号系统说明延缓（处理）事件。...
2022/8/10 20:24:35
linux shell
linux shell，Shell本身是一个用C语言编写的程序，...
2022/8/10 20:24:30
C++核心准则C.43:保证(值类型)可拷贝类有默认构造函数
C++核心准则C.43:保证(值类型)可拷贝类有默认构造函数，C.43:Ensurethatacopyable(valuetype)classhasadefaultconstructorC.43:确保(值类型)可拷贝类有默认构造函数Reason（原因）Manyyondefaultconstructorstoinitializet......
2022/8/10 20:22:41
C++核心准则C.40:如果类包含不变式，则定义构造函数
C++核心准则C.40:如果类包含不变式，则定义构造函数，C.40:DefineaconstructorifaclasshasaninvariantC.40:如果类包含不变式，则定义构造函数Reason(原因)That'swhatconstructorsarefor.这就...
2022/8/10 20:17:12
#夏日挑战赛#【ELT.ZIP】啃论文俱乐部——学术科研方法论沉淀辑
#夏日挑战赛#【ELT.ZIP】啃论文俱乐部——学术科研方法论沉淀辑，论文不论是在大家的刻板印象中，抑或是实际地阅读后都会给大家带来一种感觉。所涉及的知识量是巨大的，对背后原理的理解是具有不小挑战的，其中的公式推导是极度烧脑的。基于前面几点，论文确实是个硬骨头，因此用啃这个字来刻画论文阅读，是很恰当的。但是对于硬骨头，大家也都啃过真的“硬骨头”，其中的精华可能暗藏在骨缝之中，需要你对Mainbody的仔细阅读来发现与获取；如果莽撞的硬来，稍有不慎就会硌到牙，比如说你开始和数学公式斗争。...
2022/8/10 19:57:46
HBase集群搭建
2.修改配置 vim /home/root/hbase-2.4.11/conf/hbase-env.sh export JAVA_HOME/home/root/java8是否采用Hbase自带的zookeeper export HBASE_MANAGES_ZKfalsevim /home/root/hbase-2.4.11/conf/regionservers配置分布式Hbase的服务节点 node1 node2 node3vim /home/root/hba…...
2022/5/6 17:59:50
华为交换机配置dhcp详细配置
<Huawei>system-view -- 进去配置模式 [Huawei]dhcp enable 开启dhcp服务配置防止IP地址重复分配功能 dhcp snooping enable 在全局模式开启dhcp监听功能 （在可以接口配置） [Huawei] dhcp server ping packet 3 ping 3次包 [Huawei] dhcp ser…...
2022/5/6 17:59:49
QT入门自学
2022.5.6 1、自定义控件封装 1.1 创建QT-设计师界面类 1.2 拖拽Widget 右键提升为 -类名写入-全局包含-添加-提升 1.3 QSpinBox移动，Slider跟着移动 1.4 对外接口 setValue getValue 2、鼠标事件 2.1 鼠标进入 enterEvent 2.2 鼠标离开 leaveEvent 2.3 鼠标…...
2022/5/6 17:59:48
HTML--BOM window对象（实例：放大镜）
目录简介： 1、BOM结构 2、window对象 3、location对象 4、history对象 5、navigator对象 6、screen对象 BOM 定时器 1、定时器方法放大镜简介： BOM即浏览器对象模型（Browser Object Model），它提供了页面…...
2022/5/6 17:59:42
If you want an embedded database (H2, HSQL or Derby), please put it on the classpath.
可能是这个的问题,去掉试试,再不行重启一下idea em....我是这样解决的...
2022/5/6 17:59:40
shell函数详解，基本使用进阶使用
一、基本使用 shell中可以自定义函数，然后在脚本中可调用，但必须保证先定义再使用。 1. 函数定义 function_name () {....[return int] } # 或者 function function_name() {.... }重点： function关键字可以省略，但加上更容易…...
2022/5/6 17:59:39
element同时使用Drawer和Dialog出现多个遮罩
如果我们正使用drawer的同时又使用了dialog就会出现多个遮罩层，我们只需要在dialog上加一个属性 modal-append-to-body“false” 就可以解决 <el-dialog title"新增" :modal-append-to-body"false" > </el-dialog>如果我们出现多个…...
2022/5/6 17:58:30
汇编实现通过输入被加数与加数，实现加法
DATAS SEGMENT OP1 DW 0 OP2 DW 0 RESULT DB 20 DUP(?) CARRY DB ? BUFSIZE DB 25 ACTCHAR DB ? CHARTEXT DB 26 DUP(20H);获取储存空间 DB $ DATAS ENDS STACKS SEGMENT ;此处输入堆栈段代码 STACKS ENDS CODES SEGMEN…...
2022/5/6 17:58:01
QT 点击按钮改变输入框中文字显示（明文或密文）
今天刚好要做这个功能，但是发现网上的参考资料有点少。所以就写了这篇。效果图如下： 在这之前先讲以下QLineEdit明文和密文的写法。代码如下关于setEchoMode的几种用法//默认，输入什么即显示什么echoLineEdit->setEchoMode(QLineEdit…...
2022/5/6 17:58:00
Android中View的创建流程解析
在AppCompatActivity的onCreate方法中我们都知道setContentView这个方法是加载布局文件。这个方法使用很简单直接把layout布局文件放进去就可以了。那么具体内部是怎么将它显示到桌面的呢，今天就从setContentView()来解析一下Android中View的创建过程。打开androi…...
2022/5/6 17:57:59
SWUST OJ#978 #979 #980 二叉树的遍历
目录深度优先遍历输出利用先序遍历创建的二叉树的前序遍历序列思路代码 #978 输出利用先序遍历创建的二叉树的中序遍历序列题目思路代码 #979 输出利用先序遍历创建的二叉树的后序遍历序列题目思路代码广度优先遍历 #980 输出利用先序遍历创建的二叉树…...
2022/5/6 17:57:30

最新文章

15、ESP32 BLE

低功耗蓝牙： 低功耗蓝牙，简称 BLE，是蓝牙的省电版本。BLE 的主要应用是短距离传输少量数据（低带宽）。与经典蓝牙不同，BLE 始终保持睡眠模式，除非启动连接，这使得它消耗的功率非常低。…...

2024/4/20 0:42:30

梯度消失和梯度爆炸的一些处理方法

在这里是记录一下梯度消失或梯度爆炸的一些处理技巧。全当学习总结了如有错误还请留言，在此感激不尽。权重和梯度的更新公式如下： w w − η ⋅ ∇ w w w - \eta \cdot \nabla w ww−η⋅∇w 个人通俗的理解梯度消失就是网络模型在反向求导的时候出…...

2024/3/20 10:50:27

OpenHarmony开发-连接开发板调试应用

在 OpenHarmony 开发过程中，连接开发板进行应用调试是一个关键步骤，只有在真实的硬件环境下，我们才能测试出应用更多的潜在问题，以便后续我们进行优化。本文详细介绍了连接开发板调试 OpenHarmony 应用的操作步骤。首先&#xf…...

2024/4/19 23:50:25

自动化标准Makefile与lds

makefile的自动化，需要使用变量，以及自动变量。实行命令行与参数的分离。命令行只与变量打交道，而变量则携带不同的参数，这样，通过修改变量，命令的执行结果不同。可以简单理解为，命令行是个…...

2024/4/18 21:26:05

配置失败还原请勿关闭计算机,电脑开机屏幕上面显示，配置失败还原更改请勿关闭计算机开不了机这个问题怎么办...

解析如下：1、长按电脑电源键直至关机，然后再按一次电源健重启电脑，按F8健进入安全模式2、安全模式下进入Windows系统桌面后，按住“winR”打开运行窗口，输入“services.msc”打开服务设置3、在服务界面，选中…...

2022/11/19 21:17:18

错误使用 reshape要执行 RESHAPE，请勿更改元素数目。

%读入6幅图像（每一幅图像的大小是564*564） f1 imread(WashingtonDC_Band1_564.tif); subplot(3,2,1),imshow(f1); f2 imread(WashingtonDC_Band2_564.tif); subplot(3,2,2),imshow(f2); f3 imread(WashingtonDC_Band3_564.tif); subplot(3,2,3),imsho…...

2022/11/19 21:17:16

配置已完成请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机...

win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”问题的解决方法在win7系统关机时如果有升级系统的或者其他需要会直接进入一个等待界面，在等待界面中我们需要等待操作结束才能关机，虽然这比较麻烦，但是对系统进行配置和升级…...

2022/11/19 21:17:15

台式电脑显示配置100%请勿关闭计算机,“准备配置windows 请勿关闭计算机”的解决方法...

有不少用户在重装Win7系统或更新系统后会遇到“准备配置windows，请勿关闭计算机”的提示，要过很久才能进入系统，有的用户甚至几个小时也无法进入，下面就教大家这个问题的解决方法。第一种方法：我们首先在左下角的“开始…...

2022/11/19 21:17:14

win7 正在配置请勿关闭计算机,怎么办Win7开机显示正在配置Windows Update请勿关机...

置信有很多用户都跟小编一样遇到过这样的问题，电脑时发现开机屏幕显现“正在配置Windows Update，请勿关机”(如下图所示)，而且还需求等大约5分钟才干进入系统。这是怎样回事呢？一切都是正常操作的，为什么开时机呈现“正…...

2022/11/19 21:17:13

准备配置windows 请勿关闭计算机蓝屏,Win7开机总是出现提示“配置Windows请勿关机”...

Win7系统开机启动时总是出现“配置Windows请勿关机”的提示，没过几秒后电脑自动重启，每次开机都这样无法进入系统，此时碰到这种现象的用户就可以使用以下5种方法解决问题。方法一：开机按下F8，在出现的Windows高级启动选…...

2022/11/19 21:17:12

准备windows请勿关闭计算机要多久,windows10系统提示正在准备windows请勿关闭计算机怎么办...

有不少windows10系统用户反映说碰到这样一个情况，就是电脑提示正在准备windows请勿关闭计算机，碰到这样的问题该怎么解决呢，现在小编就给大家分享一下windows10系统提示正在准备windows请勿关闭计算机的具体第一种方法：1、2、依次…...

2022/11/19 21:17:11

配置已完成请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”的解决方法...

今天和大家分享一下win7系统重装了Win7旗舰版系统后，每次关机的时候桌面上都会显示一个“配置Windows Update的界面，提示请勿关闭计算机”，每次停留好几分钟才能正常关机，导致什么情况引起的呢？出现配置Windows Update…...

2022/11/19 21:17:10

电脑桌面一直是清理请关闭计算机,windows7一直卡在清理请勿关闭计算机-win7清理请勿关机,win7配置更新35%不动...

只能是等着，别无他法。说是卡着如果你看硬盘灯应该在读写。如果从 Win 10 无法正常回滚，只能是考虑备份数据后重装系统了。解决来方案一：管理员运行cmd：net stop WuAuServcd %windir%ren SoftwareDistribution SDoldnet start WuA…...

2022/11/19 21:17:09

计算机配置更新不起,电脑提示“配置Windows Update请勿关闭计算机”怎么办？

原标题：电脑提示“配置Windows Update请勿关闭计算机”怎么办？win7系统中在开机与关闭的时候总是显示“配置windows update请勿关闭计算机”相信有不少朋友都曾遇到过一次两次还能忍但经常遇到就叫人感到心烦了遇到这种问题怎么办呢？一般的方…...

2022/11/19 21:17:08

计算机正在配置无法关机,关机提示 windows7 正在配置windows 请勿关闭计算机，然后等了一晚上也没有关掉。现在电脑无法正常关机...

关机提示 windows7 正在配置windows 请勿关闭计算机 ，然后等了一晚上也没有关掉。现在电脑无法正常关机以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容，让我们赶快一起来看一下吧！关机提示 windows7 正在配…...

2022/11/19 21:17:05

钉钉提示请勿通过开发者调试模式_钉钉请勿通过开发者调试模式是真的吗好不好用...

钉钉请勿通过开发者调试模式是真的吗好不好用更新时间：2020-04-20 22:24:19　浏览次数：729次区域：南阳 > 卧龙列举网提醒您：为保障您的权益，请不要提前支付任何费用！虚拟位置外设器!!轨迹模拟&虚拟位置外设神器专业用于：钉钉，外勤365，红圈通，企业微信和…...

2022/11/19 21:17:05

配置失败还原请勿关闭计算机怎么办,win7系统出现“配置windows update失败还原更改请勿关闭计算机”，长时间没反应，无法进入系统的解决方案...

前几天班里有位学生电脑(windows 7系统)出问题了，具体表现是开机时一直停留在“配置windows update失败还原更改请勿关闭计算机”这个界面，长时间没反应，无法进入系统。这个问题原来帮其他同学也解决过，网上搜了不少资料&#x…...

2022/11/19 21:17:04

一个电脑无法关闭计算机你应该怎么办,电脑显示“清理请勿关闭计算机”怎么办？...

本文为你提供了3个有效解决电脑显示“清理请勿关闭计算机”问题的方法，并在最后教给你1种保护系统安全的好方法，一起来看看！电脑出现“清理请勿关闭计算机”在Windows 7(SP1)和Windows Server 2008 R2 SP1中，添加了1个新功能在“磁…...

2022/11/19 21:17:03

请勿关闭计算机还原更改要多久,电脑显示:配置windows更新失败，正在还原更改，请勿关闭计算机怎么办...

许多用户在长期不使用电脑的时候，开启电脑发现电脑显示：配置windows更新失败，正在还原更改，请勿关闭计算机。。.这要怎么办呢？下面小编就带着大家一起看看吧！如果能够正常进入系统，建议您暂时移…...

2022/11/19 21:17:02

还原更改请勿关闭计算机要多久,配置windows update失败还原更改请勿关闭计算机，电脑开机后一直显示以...

配置windows update失败还原更改请勿关闭计算机，电脑开机后一直显示以以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容，让我们赶快一起来看一下吧！配置windows update失败还原更改请勿关闭计算机&#x…...

2022/11/19 21:17:01

电脑配置中请勿关闭计算机怎么办,准备配置windows请勿关闭计算机一直显示怎么办【图解】...

不知道大家有没有遇到过这样的一个问题，就是我们的win7系统在关机的时候，总是喜欢显示“准备配置windows，请勿关机”这样的一个页面，没有什么大碍，但是如果一直等着的话就要两个小时甚至更久都关不了机，非常…...

2022/11/19 21:17:00

正在准备配置请勿关闭计算机,正在准备配置windows请勿关闭计算机时间长了解决教程...

当电脑出现正在准备配置windows请勿关闭计算机时，一般是您正对windows进行升级，但是这个要是长时间没有反应，我们不能再傻等下去了。可能是电脑出了别的问题了，来看看教程的说法。正在准备配置windows请勿关闭计算机时间长了方法一…...

2022/11/19 21:16:59

配置失败还原请勿关闭计算机,配置Windows Update失败，还原更改请勿关闭计算机...

我们使用电脑的过程中有时会遇到这种情况，当我们打开电脑之后，发现一直停留在一个界面：“配置Windows Update失败，还原更改请勿关闭计算机”，等了许久还是无法进入系统。如果我们遇到此类问题应该如何解决呢&#xff0…...

2022/11/19 21:16:58

如何在iPhone上关闭“请勿打扰”

Apple’s “Do Not Disturb While Driving” is a potentially lifesaving iPhone feature, but it doesn’t always turn on automatically at the appropriate time. For example, you might be a passenger in a moving car, but your iPhone may think you’re the one dri…...

2022/11/19 21:16:57