Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7233 | Accepted: 2173 |
Description
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
Output
Sample Input
2
3
1 2 3
8
1 5 6 7 9 12 14 17
Sample Output
Bob will win
Georgia will win
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int MAX_N = ;
int p[MAX_N]; int main()
{
int t;
scanf("%d",&t);
while(t--) {
int N;
scanf("%d",&N);
for(int i = ; i < N; ++i) {
scanf("%d",&p[i]);
}
if(N % == ) p[N++] = ;
sort(p, p + N); int x = ;
for(int i = ; i + < N; i += ) {
x ^= (p[i + ] - p[i] - );
} if(x == ) printf("Bob will win\n");
else printf("Georgia will win\n");
}
//cout << "Hello world!" << endl;
return ;
}
poj 1704的更多相关文章
-
POJ 1704 Georgia and Bob(阶梯博弈+证明)
POJ 1704 题目链接 关于阶梯博弈有如下定理: 将所有奇数阶梯看作n堆石头,做Nim,将石头从奇数堆移动到偶数堆看作取走石头,同样地,异或值不为0(利己态)时,先手必胜. 定理证明看此博:htt ...
-
poj 1704 Georgia and Bob(阶梯博弈)
Georgia and Bob Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 9363 Accepted: 3055 D ...
-
阶梯博弈&;POJ 1704
阶梯博弈: 先借用别人的一幅图片.(1阶梯之前还有一个0阶梯未画出) 阶梯博弈的最初定义是这样的:每一个阶梯只能向它的前一个阶梯移动本阶梯的点,直至最后无法移动的为输. 那么,利用NIM,只计算奇数级 ...
-
POJ 1704 Georgia and Bob (Nim游戏变形)
题目:http://poj.org/problem?id=1704 思路:Nim游戏策略,做如下转换,如果N是偶数,则两两配对,将两个数之间的格子数(距离)看做成这一堆石头的数量. 如果N是奇数,则将 ...
-
POJ 1704 Georgia and Bob【博弈】
题目链接: http://poj.org/problem?id=1704 题意: 给定棋子及其在格子上的坐标,两个人轮流选择一个棋子向左移动,每次至少移动一格,但是不可以碰到其他棋子.无路可走的时候视 ...
-
【POJ 1704】 Georgia and Bob
[题目链接] http://poj.org/problem?id=1704 [算法] 阶梯博弈 [代码] #include <algorithm> #include <bitset& ...
-
【poj 1704】Georgia and Bob
Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 9776 Accepted: 3222 Description Georgia a ...
-
poj 1704 阶梯博弈
转自http://blog.sina.com.cn/s/blog_63e4cf2f0100tq4i.html 今天在POJ做了一道博弈题..进而了解到了阶梯博弈...下面阐述一下我对于阶梯博弈的理解. ...
-
poj 1704 Georgia and Bob(阶梯博弈)
Georgia and Bob Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8656 Accepted: 2751 D ...
随机推荐
-
Cordova webapp实战开发:(1)为什么选择 Cordova webapp?
很长时间没有专注写代码了,即使写点代码也主要是写写敏捷个人app,这个App主体内容是我用了一周的时间,使用PhoneGap+JQueryMobile搭建的,之所以会比较快的完成,是因为11年我在做建 ...
-
算法:欧几里得求最大公约数(python版)
#欧几里得求最大公约数 #!/usr/bin/env python #coding -*- utf:8 -*- #iteration def gcd(a,b): if b==0: return a e ...
-
objective-c可变字典
1 #pragma mark *****************************字典******************************** 2 // 字典:通过ke ...
-
Android(java)学习笔记232:Android进程间通讯(IPC)之AIDL
一.IPC inter process communication 进程间通讯 二.AIDL android interface defination language 安卓接口定义语言 满 ...
-
idea无法正常使用SVN的解决方法
问题描述: IntelliJ IDEA安装之后,使用SVN进行提交或更新以及检出代码的时候会出现如下错误: Cannot load supported formats: Cannot run prog ...
-
基础测试jmeter5.0+badboy(从小白到入门)
1]测试工具jmeter环境安装 1.1]安装jdk环境 1:必须安装jdk8.0(我尝试安装最新版本不行,好像当时没有配置好.之后安装8.0遍可以正常运行)下载地址:单击此段 配置jdk环境:鼠标右 ...
-
mysql _触发器
MySQL 触发器 MySQL包含对触发器的支持.触发器是一种与表操作有关的数据库对象,当触发器所在表上出现指定事件时,将调用该对象,即表的操作事件触发表上的触发器的执行. 1.创建触发器在MySQL ...
-
Vue中 $ref 的用法
说明:vm.$refs 一个对象,持有已注册过 ref 的所有子组件(或HTML元素)使用:在 HTML元素 中,添加ref属性,然后在JS中通过vm.$refs.属性来获取注意:如果获取的是一个子组 ...
-
c# 通过反射输出成员变量以及成员变量的值
/*** @Author rexzhao* 工具类 仅限于* public variable*/using System.Collections;using System.Collections.Ge ...
-
CentOS 7使用yum安装PHP5.6
删除旧php包 yum remove php.x86_64 php-cli.x86_64 php-common.x86_64 php-gd.x86_64 php-ldap.x86_64 php-mbs ...