HDU-1527 取石子游戏

2016年04月17日 |

acm

| acm

• 题目：
• 代码：
• 解析&吐槽：

题目：

取石子游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5596 Accepted Submission(s): 2922


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
NOI


Recommend
LL

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//
#include<iostream>
#include <cmath>
#include <map>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b;
    while (cin >> a >> b)
    {
        if (a > b)
            swap(a, b);
        int k = b - a;
        if ((int)(k*(1 + sqrt(5)) / 2.0) == a)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
}

解析&吐槽：

这是一道关于威佐夫博弈的题，关于威佐夫博弈的资料请自行百度，其实原理我没看懂_(:зゝ∠)_\ 不过用法我倒是大致明白了。对于左右两堆石子，令

a[k]=(int)(k*(1+sqrt(5))/2.0);
b[k]=a[k]+k;

其中 k 是编号，满足此关系的一对石子堆(a,b)称为奇异局势，如果两个人都采用正确操作， 那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。