POJ 1704 Georgia and Bob

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: 

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

这道题绝对是NIM的加强版。

初看一下，这道题目的棋子移动还要收到其他棋子的限制，这让人难以下手。但是稍微想一下，就想出了一些很神奇的东东

题目的问题可以让人明白这是博弈，当我们面对一道题时，不是想着把一种算法去修改去适应这道题目，而是改变这个题目的要求，让他去适应一种算法，因为是N组数据，我很快想到NIM。是的，就是NIM，当然这道题目跟NIM还是有一定的区别，对于取石子游戏，石子是有减无增的。我们可以改变题目的模型适应它。首先就是以两个两个相邻的棋子为一组，他们的差即A[I]-A[I-1]-1为石子的数量。但是我们马上会想到，如果左边的石子移动了，那么这个差不就改变了么，这还是NIM么？我们变化策略，当对手将左边的石子移动K，那么我们就把右边的石子也移动K，YES,IT'S EASY！如果对手移动了右边的棋子，哈哈，那不就是我们可以和对手玩取石子游戏了，正解！

另外注意，构造模型时候可能出现组数不是偶数，就是还剩一个棋子，那么就直接A[1]-1即可！

博弈不过如此

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int a[1001],s[1001];

bool flag;

int cmp(int a,int b)

{

    if(a==b)   flag=false;

    return a<b;

}

int main()

{

    int T,n,x,sum;

    while(scanf("%d",&T)!=EOF)

    {

        while(T--)

        {

            memset(s,0,sizeof(s));

            scanf("%d",&n);

            flag=true;

            for(int i=1;i<=n;i++)

                scanf("%d",&a[i]);

            sort(a+1,a+n+1,cmp);

            int i,j;

            for(i=n,j=1;i>=2;i-=2,j++)  s[j]=a[i]-a[i-1]-1;

            if(i==1) s[j++]=a[1]-1;

            //if(!flag)  printf("Not sure/n");

            //else

            {

                for(int i=1;i<j;i++)

                {

                    if(i==1) sum=s[i];

                    else sum=sum^s[i];

                }

                if(sum==0)  printf("Bob will win/n");

                else

                printf("Georgia will win/n");

            }

        }

    }

    return 0;

}