poj 1067ウィゾフゲーム

2565 ワード

http://poj.org/problem?id=1067
NEUトレーニングから抜粋
•奇異な情勢と非奇異な情勢を分析する:
•我々は(ak,bk)(ak≦bk,k=0,1,2,...,n)で2つの荷物の数を表し、情勢と呼ぶ
•甲が(0,0)に直面すると、甲が負けてしまうことを奇異情勢と呼ぶ.前の奇異情勢は(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)である.
•a 0=b 0=0,akは前に現れなかった最小自然数であり,bk=ak+kであることがわかる.
•奇異な情勢には、次の3つの性質があることがわかりました.
•    1.いかなる自然数も1つの奇異な情勢に含まれている.
•    akは前に現れなかった最小自然数であるため,ak>ak−1があり,bk=ak+k>ak−1+k−1=bk−1>ak−1がある.従って,この性質は成立する.
•   2.任意の操作で奇異な情勢を非奇異な情勢に変えることができる.
•   実際、奇異情勢(ak,bk)のある成分だけを変えると、別の成分が他の奇異情勢にあるはずがないので、必然的に非奇異情勢である.(ak,bk)の2つの成分を同時に減少させると、その差が変わらず、他の奇異情勢の差であるはずがないため、非奇異情勢である.
•    
•3.適切な方法で、非特異な情勢を特異な情勢に変えることができます.

•    仮に直面する情勢は(a,b)であり、b=aであれば、同時に2つの山からa個の物体を取り出すと、奇異な情勢(0,0)になる.
•a=ak,b>bkの場合、bを取り出す  – bk個の物体は、奇異な情勢になる.
•a=ak,b•a>ak,b=ak+kの場合、第1の山から余分な数のa-akを取ればよい.
•a•1つ目は、a=aj(j
•so、二人とも正しい操作を採用すれば、非奇異な情勢に直面して、先取り者は必ず勝つ;逆に、後取り者は勝つ.
•では、一つの情勢(a,b)に任せて、それが奇異な情勢であるかどうかをどのように判断しますか?私たちは以下の公式を持っています.
•    ak =[k(1+√5)/2],bk= ak + k  (k=0,1,2,...,n角括弧は整数関数を表す)
•奇妙なことに、黄金分割数(1+√5)/2=1が出現した.618....したがって、ak,bkからなる矩形は黄金矩形に近似し、2/(1+√5)=(√5-1)/2のため、j=[a(√5-1)/2]を先に求めることができ、a=[j(1+5)/2]あ、ではa=aj、bj=aj+j、等しくなければa=aj+1、bj+1=aj+1+j+1、そうでなければ奇異な情勢ではない.そして上記の法則に従って行うと、必ず奇異な情勢に遭遇する.

-証明:これは少し長くて、気持ち悪いです.http://wenku.baidu.com/link?url=T6aKvdjY99YtfcOScwYXx3Hh7jrCYPAwlzYHu89q8Azv2tXswwH6NaoGuJpqQVGY8Nn5H2T3utu3RZiY1QygxZix--6knNb8rfOcmcjEPKa
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdin)

int main()
{
    int a,b,k;
    while(~scanf("%d%d",&a,&b))
    {
        if(a>b)swap(a,b);
        k=b-a;
        if(a==(int)(k*(1.0+sqrt(5.0))/2))puts("0");
        else puts("1");
    }
    return 0;
}