hdu 4315 Climbing the Hill(阶梯博弈转nim博弈)
2024-10-12 11:12:07
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?
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
1 2 4
2 1
100 200
Sample Output
Bob
Alice
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
代码:
#include<cstring>
#include<cstdio>
#include<cstdlib>
int aa[];
int n,k;
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=;i<n;i++)
scanf("%d",&aa[i]);
int ans=;
if(k==)
{
puts("Alice");
continue;
}
if(n%==) //偶数堆
{
for(int i=;i<n;i+=)
ans^=(aa[i]-aa[i-]-);
}
else
{
if(k==) ans=aa[]-;
else ans=aa[];
for(int i=;i<n;i+=)
ans^=(aa[i]-aa[i-]-);
}
if(ans) puts("Alice");
else puts("Bob");
}
return ;
}
最新文章
- 七天学会ASP.NET MVC(七)——创建单页应用
- SQL PASS将于8月24日在北京中医药大学举办线下活动
- 升级10.11.6后CocoaPods的坑,之前10.11.4已经安装好的,居然没了Failed to locate Homebrew!
- Steganography-图片隐写术
- Shell_参数替换(転)
- centos升级mysql至5.7
- -webkit-appearance: none;去处select默认小箭头样式
- MYSQL 查询缓存
- Centos6.8 安装nginx
- solr增加中文分析器
- RabbitMQ服务端配置详解
- 收藏:IPicture总结
- jQuery验证插件使用初步
- JAVA Spring JdbcTemplate ( 以 SQLSERVER 为例 ) 的简单使用
- Oracle的 EXEC SQL CONTEXT学习
- DDD实战成绩管理---需求分析
- Apache-solr
- DWR 3.0 入门示例教程
- 条目二十一《总是让比较函数在等值情况下返回false》
- Qt-事件处理-鼠标事件