hdu4315 Climbing the Hill（博弈论）

Climbing the Hill

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 356    Accepted Submission(s): 145

Problem Description

Alice and Bob are playing a game called "Climbing the Hill". The game board consists of cells arranged vertically, as the figure below, while the top cell indicates the top of hill. There are several persons at different cells, and there is one special people, that is, the king. Two persons can't occupy the same cell, except the hilltop.

At one move, the player can choose any person, who is not at the hilltop, to climb up any number of cells. But the person can't jump over another one which is 
above him. Alice and Bob move the persons alternatively, and the player who move the king to the hilltop will win. 



Alice always move first. Assume they play optimally. Who will win the game?

 

 

Input

There are several test cases. The first line of each test case contains two integers N and k (1 <= N <= 1000, 1 <= k <= N), indicating that there are N persons on the
hill, and the king is the k-th nearest to the top. N different positive integers followed in the second line, indicating the positions of all persons. (The hilltop is No.0 cell, the cell below is No.1, and so on.) These N integers are ordered increasingly, more than 0 and less than 100000.

 

 

Output

If Alice can win, output "Alice". If not, output "Bob".

 

 

Sample Input

3 3

1

2

4

2 1

100

200

 

 

Sample Output

Bob Alice

Hint

The figure illustrates the first test case. The gray cell indicates the hilltop. The circles indicate the persons, while the red one indicates the king. The first player Alice can move the person on cell 1 or cell 4 one step up, but it is not allowed to move the person on cell 2.

 

 

Source

2012 Multi-University Training Contest 2

 

题意：如上图所示：有 n 个球分别在 n 个不同的位置，Alice 和 Bob 依次选择一个球向上移动，上面有球不能越过，谁最后把红球移出谁就赢！

分析：

 1、n 为偶数时：问题简化一下，假设全都是黄球，谁把最后一个球移出谁就赢

（a1,a2） (a3,a4)  …… ( a(2*n-1) , a(2*n) ) ……（a(n-1),an）其中第 i 个球与第 i+1 个球是相邻的，i 为基数，谁面对这个状态谁就必输。

理由很简单，先手移动第 i 个球，后手移动第 i+1 个球，使之仍然保持必赢状态。

回到原问题谁先移出红球谁就赢，假设红球不是第一个球（因为第一个球Alice直接就赢了）

很显然如果红球在偶数位置后手必赢，如果在基数 i 位置，则只需将 第 i-1 个球移到第一个位置就ok了。

所以与红球位置无关。至于产生这个状态（a1,a2） (a3,a4)  …… ( a(2*n-1) , a(2*n) ) ……（a(n-1),an），那么就是简单的 Nim问题了

2、n 为基数时：假设红球是第1、2个球。

（a1） (a2,a3)（a4,a5）…… (a(2*n),a(2*n+1)) …… (a(n-1),an) 谁面对这个状态必赢！理由是先手直接把 a1 取走然后就变成上面的情况了，

如果红球在第 2 个位置那么就是必输状态。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 1010

using namespace std;

int a[MAXN];

int main()
{
    int n,k,i;
    while(cin>>n>>k)
    {
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        if(k==1)
        {
            cout<<"Alice"<<endl;
            continue;
        }
        int t;
        if(n%2==0)
        {
            t=a[2]-a[1]-1;
            for(i=4;i<=n;i=i+2) t=t^(a[i]-a[i-1]-1);
            if(t==0)cout<<"Bob"<<endl;
            else cout<<"Alice"<<endl;
        }
        else
        {
            t=a[1];
            if(k==2) t-=1;
            for(i=3;i<=n;i=i+2) t=t^(a[i]-a[i-1]-1);
            if(t==0)cout<<"Bob"<<endl;
            else cout<<"Alice"<<endl;
        }
    }
    return 0;
}