hdu 1527, poj 1067 돌 채취 게임 위 조 프 보 이 (Wythoff Game)

두 무더기 의 돌 은 매번 한 무더기 에서 임의의 것 을 가 져 가 거나 두 무더기 가 동시에 임의의 것 을 가 져 가 먼저 승 부 를 구 할 수 있다.표준 위 조 프 박 혁 (Wythoff Game) 모델, 다음 운반 모델 증명 과정..http://blog.csdn.net/acm_cxlove/article/details/7854530
위 조 프 보 혁 (Wythoff Game): 두 무더기 가 각각 몇 개의 물건 이 있 습 니 다. 두 사람 은 돌아 가면 서 한 무더기 또는 동시에 두 더미 에서 똑 같은 물건 을 찾 습 니 다. 매번 에 적어도 하 나 를 취하 고 다 자 는 제한 하지 않 으 며 마지막 에 빛 을 얻 는 사람 이 이 기 는 것 을 규정 합 니 다.    이런 상황 하에 서 는 꽤 복잡 하 다.우 리 는 (ak, bk) (ak ≤ bk, k = 0, 1, 2,..., n) 으로 두 무더기 의 물품 의 수량 을 표시 하고 그것 을 정세 라 고 부른다. 만약 에 갑 이 (0, 0) 직면 하면 갑 이 이미 졌 다. 이런 정 세 를 우 리 는 기이 한 정세 라 고 부른다. 앞의 몇 가지 기이 한 정 세 는 (0, 0), (1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18),(12,20).
    이 를 통 해 알 수 있 듯 이 a0 = b0 = 0, ak 는 앞에서 나타 나 지 않 은 최소 자연수 이 고 bk = ak + k 는 기이 한 정 세 는 다음 과 같은 세 가지 특징 이 있다.
    1. 모든 자연 수 는 하나의 기이 한 상황 에 포함 되 어 있다.    ak 는 앞에서 나타 나 지 않 은 최소 자연수 이기 때문에 ak > ak - 1 이 있 고 bk = ak + k > ak - 1 + k - 1 = bk - 1 > ak - 1 이 있 습 니 다. 그래서 성질 1. 성립 됩 니 다.    2. 임의로 조작 하면 기이 한 정 세 를 기이 하지 않 은 정세 로 바 꿀 수 있다.    사실 기이 한 정세 (ak, bk) 의 한 분량 만 바 꾸 면 다른 분량 은 다른 기이 한 정세 에 있 을 수 없 기 때문에 기이 한 정세 가 아 닐 수 밖 에 없다. (ak, bk) 의 두 분량 을 동시에 줄 이면 그 차이 가 변 하지 않 고 그의 기이 한 정세의 차이 일 수 없 기 때문에 기이 한 정세 도 아니다.    3. 적당 한 방법 으로 기이 하지 않 은 정 세 를 기이 한 정세 로 바 꿀 수 있다.
    만약 에 직면 한 상황 이 (a, b) 이 라 고 가정 하면 b = a 는 두 더미 에서 a 개의 물 체 를 동시에 가 져 가면 기이 한 상황 (0, 0) 으로 변 한다. 만약 에 a = ak, b > bk 라면 b 를 가 져 간다.  – bk 개 물 체 는 기이 한 정세 로 변 한다. 만약 a = ak,  b < bk, 동시에 두 더미 에서 ak – ab – ak 개 물 체 를 가 져 가 기이 한 상황 (ab – ak, ab – ak + b – ak) 으로 변 한다. 만약 a > ak, b = ak + k 라면 첫 번 째 더미 에서 여분의 수량 a – ak 를 가 져 가면 된다. 만약 a < ak, b = ak + k, 두 가지 상황 으로 나 뉘 면 첫 번 째, a = aj (j < k), 두 번 째 더미 에서 b – bj 를 가 져 가면 된다. 두 번 째, a = bj (j < k), 두 번 째 더미 에서 b – a j 를 가 져 가면 됩 니 다.
    위의 성격 을 통 해 알 수 있 듯 이 두 사람 이 모두 정확 한 조작 을 한다 면 기이 하지 않 은 상황 에 직면 하여 먼저 이 기 는 사람 은 반드시 이 기 는 것 이 고, 반대로 이 기 는 사람 이 이 기 는 것 이다.
    그렇다면 하나의 정세 (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, 그렇지 않 으 면 기이 한 상황 이 아니다. 그리고 상기 법칙 에 따라 진행 하면 반드시 기이 한 상황 을 만 날 것 이다.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int n,m;
int x,y;
const double g=1.61803398874;
int main()
{
    while(~scanf("%d%d",&x,&y))
    {
        if (x>y) swap(x,y);
        double k=y-x;
        if (int(k*g)==x) puts("0");
        else puts("1");
    }
    return 0;
}