poj 1704

时间:2021-09-07 20:47:42
Georgia and Bob
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 7233   Accepted: 2173

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 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

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

Sample Output

Bob will win
Georgia will win

Source

 
转化成nim游戏,两个石子之间的间隔就是石子个数
 #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的更多相关文章

  1. POJ 1704 Georgia and Bob(阶梯博弈&plus;证明)

    POJ 1704 题目链接 关于阶梯博弈有如下定理: 将所有奇数阶梯看作n堆石头,做Nim,将石头从奇数堆移动到偶数堆看作取走石头,同样地,异或值不为0(利己态)时,先手必胜. 定理证明看此博:htt ...

  2. poj 1704 Georgia and Bob&lpar;阶梯博弈&rpar;

    Georgia and Bob Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 9363   Accepted: 3055 D ...

  3. 阶梯博弈&amp&semi;POJ 1704

    阶梯博弈: 先借用别人的一幅图片.(1阶梯之前还有一个0阶梯未画出) 阶梯博弈的最初定义是这样的:每一个阶梯只能向它的前一个阶梯移动本阶梯的点,直至最后无法移动的为输. 那么,利用NIM,只计算奇数级 ...

  4. POJ 1704 Georgia and Bob (Nim游戏变形)

    题目:http://poj.org/problem?id=1704 思路:Nim游戏策略,做如下转换,如果N是偶数,则两两配对,将两个数之间的格子数(距离)看做成这一堆石头的数量. 如果N是奇数,则将 ...

  5. POJ 1704 Georgia and Bob【博弈】

    题目链接: http://poj.org/problem?id=1704 题意: 给定棋子及其在格子上的坐标,两个人轮流选择一个棋子向左移动,每次至少移动一格,但是不可以碰到其他棋子.无路可走的时候视 ...

  6. 【POJ 1704】 Georgia and Bob

    [题目链接] http://poj.org/problem?id=1704 [算法] 阶梯博弈 [代码] #include <algorithm> #include <bitset& ...

  7. 【poj 1704】Georgia and Bob

    Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 9776 Accepted: 3222 Description Georgia a ...

  8. poj 1704 阶梯博弈

    转自http://blog.sina.com.cn/s/blog_63e4cf2f0100tq4i.html 今天在POJ做了一道博弈题..进而了解到了阶梯博弈...下面阐述一下我对于阶梯博弈的理解. ...

  9. poj 1704 Georgia and Bob(阶梯博弈)

    Georgia and Bob Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 8656   Accepted: 2751 D ...

随机推荐

  1. Cordova webapp实战开发:(1)为什么选择 Cordova webapp?

    很长时间没有专注写代码了,即使写点代码也主要是写写敏捷个人app,这个App主体内容是我用了一周的时间,使用PhoneGap+JQueryMobile搭建的,之所以会比较快的完成,是因为11年我在做建 ...

  2. 算法:欧几里得求最大公约数(python版)

    #欧几里得求最大公约数 #!/usr/bin/env python #coding -*- utf:8 -*- #iteration def gcd(a,b): if b==0: return a e ...

  3. objective-c可变字典

     1 #pragma mark *****************************字典********************************  2 //        字典:通过ke ...

  4. Android(java)学习笔记232:Android进程间通讯(IPC)之AIDL

    一.IPC inter process communication  进程间通讯 二.AIDL android  interface  defination  language  安卓接口定义语言 满 ...

  5. idea无法正常使用SVN的解决方法

    问题描述: IntelliJ IDEA安装之后,使用SVN进行提交或更新以及检出代码的时候会出现如下错误: Cannot load supported formats: Cannot run prog ...

  6. 基础测试jmeter5&period;0&plus;badboy(从小白到入门)

    1]测试工具jmeter环境安装 1.1]安装jdk环境 1:必须安装jdk8.0(我尝试安装最新版本不行,好像当时没有配置好.之后安装8.0遍可以正常运行)下载地址:单击此段 配置jdk环境:鼠标右 ...

  7. mysql &lowbar;触发器

    MySQL 触发器 MySQL包含对触发器的支持.触发器是一种与表操作有关的数据库对象,当触发器所在表上出现指定事件时,将调用该对象,即表的操作事件触发表上的触发器的执行. 1.创建触发器在MySQL ...

  8. Vue中 &dollar;ref 的用法

    说明:vm.$refs 一个对象,持有已注册过 ref 的所有子组件(或HTML元素)使用:在 HTML元素 中,添加ref属性,然后在JS中通过vm.$refs.属性来获取注意:如果获取的是一个子组 ...

  9. c&num; 通过反射输出成员变量以及成员变量的值

    /*** @Author rexzhao* 工具类 仅限于* public variable*/using System.Collections;using System.Collections.Ge ...

  10. CentOS 7使用yum安装PHP5&period;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 ...