poj 1067 取石子游戏

超、凢脫俗 2022-08-03 14:40 127阅读 0赞

取石子游戏

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 37035</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 12559</td> 
  </tr> 
 </tbody> 
</table>

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][]

威佐夫博弈，不懂，暂时先记住。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int main()
    {
        int n,m;
        const double r=(1+sqrt(5))/2.0; //听说这有黄金矩形？
        while(cin>>n>>m)
        {
            if(n>m)swap(n,m);
            int k=m-n;
            if(n!=(int)(k*r))
            {
                puts("1");
    
            }
            else puts("0");
        }
        return 0;
    }

[NOI]: http://poj.org/searchproblem?field=source&key=NOI