hdu 4315 Climbing the Hill(阶梯博弈转nim博弈)

Climbing the Hill

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

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.

Author

TJU

Source

2012 Multi-University Training Contest 2

代码:

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 int aa[1005];
 5 int n,k;
 6 int main()
 7 {
 8   while(scanf("%d%d",&n,&k)!=EOF)
 9   {
10        for(int i=0;i<n;i++)
11       scanf("%d",&aa[i]);
12        int ans=0;
13      if(k==1)
14      {
15        puts("Alice");
16        continue;
17      }
18      if(n%2==0)  //偶数堆
19      {
20        for(int i=1;i<n;i+=2)
21          ans^=(aa[i]-aa[i-1]-1);
22      }
23      else
24      {
25          if(k==2) ans=aa[0]-1;
26          else     ans=aa[0];
27          for(int i=2;i<n;i+=2)
28            ans^=(aa[i]-aa[i-1]-1);
29      }
30      if(ans)  puts("Alice");
31      else puts("Bob");
32   }
33   return 0;
34 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

POJ-1458 Common Subsequence(线性动规,最长公共子序列问题)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...

3277
来自专栏ml

poj-------------(2752)Seek the Name, Seek the Fame(kmp)

Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Tot...

2767
来自专栏算法修养

HDU 5675 ztr loves math

ztr loves math Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65...

4046
来自专栏ml

HDUOJ---大菲波数

大菲波数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

29611
来自专栏ml

HDUOJ-----3591The trouble of Xiaoqian

The trouble of Xiaoqian Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

2434
来自专栏算法修养

HDU 1695 GCD (欧拉函数,容斥原理)

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

2662
来自专栏ml

POJ--Strange Way to Express Integers

Strange Way to Express Integers Time Limit: 1000MS Memory Limit: 131072K ...

2817
来自专栏小樱的经验随笔

HDU 2561 第二小整数

第二小整数 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

3418
来自专栏HansBug's Lab

3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

3278
来自专栏算法修养

CodeForces Roads not only in Berland(并查集)

H - Roads not only in Berland Time Limit:2000MS     Memory Limit:262144KB    ...

2515

扫码关注云+社区

领取腾讯云代金券