取石子游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3717 Accepted Submission(s): 1868
Problem Description
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
Input
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。
Output
输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。
Sample Input
2 1 8 4 4 7
Sample Output
0 1 0
Source
裸威佐夫博奕,一直没搞明白,就是代码简单
假设面对的局势是(a,b),若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0);如果a = ak ,b > bk 那么,取走b - bk个物体,即变为奇异局势;如果 a = ak , b < bk 则同时从两堆中拿走a-a[b-a] 个物体变为奇异局势( a[b-a], b-a+a[b-a]);如果a > ak ,b= ak + k 则从第一堆中拿走多余的数量a - ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k)从第二堆里面拿走 b - bj 即可;第二种,a=bj (j < k)从第二堆里面拿走 b - aj 即可。
证明见 : http://baike.baidu.com/view/1952620.htm?fr=aladdin
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n,m;
while(cin >> n >> m)
{
if(n > m)
{
int t;
t = n;
n = m;
m = t;
}
double p = m - n;
int mm = (sqrt(5.0)+1)*p / 2.0;
if(mm == n)
{
cout << "0" << endl;
}
else
{
cout << "1" << endl;
}
}
return 0;
}
标签:HDU,石子,两堆,ak,博弈论,000,bk,int,1527 From: https://blog.51cto.com/u_14834528/6210678