Snowdream

問(wèn)題：
有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者。

碰到這道題時(shí)我的思路：

設(shè)集合A, B分別為先手能贏和后手能贏的二元無(wú)序?qū)?x,y)的集合

先從最基礎(chǔ)的開(kāi)始考慮，(n,0) (n,n) 屬于A，因?yàn)檫@樣的情況先手肯定能贏（n為正整數(shù)，下同）

如果存在(a,b)，對(duì)于一切n，(a-n,b-n)均屬于A，則(a,b)屬于B
很容易找到一個(gè)(2,1)，這是后手肯定能贏的情況

接下來(lái)從先手的角度分析，如果他能在移動(dòng)石子后留給對(duì)手(2,1)個(gè)石子，那么他就能贏，于是
(2+n,1) (2+n,1+n) (2,1+n) 均屬于 A

找出一個(gè)不屬于A的最小對(duì)，(5,3)， 這個(gè)元素肯定屬于B集合，因?yàn)閺闹腥我馊〕鲈睾蟮慕Y(jié)果肯定屬于A集合
相應(yīng)的，(5+n, 3) (5, 3+n), (5+n, 3+n) 均屬于A

這時(shí)發(fā)現(xiàn)，B集合相對(duì)A集合元素少很多，只要找出B集合中元素的特征，就能解決這個(gè)問(wèn)題。

一旦B中包含(x,y)對(duì)，A中就會(huì)相應(yīng)的包含(x, y+n), (x+n, y), (x+n,y+n)
由此想出一種構(gòu)造B集合的方法，設(shè)當(dāng)前構(gòu)造出的集合為S，a為不在S中的最小的數(shù)，即
a = MIN{ x | x 不屬于 (p, q), 對(duì)于一切(p, q)屬于S }
則把(a, a+gap)加入B中，其中g(shù)ap是當(dāng)前S中所有對(duì)之差的最小值+1
 
 構(gòu)造出的序列為
 (1,2) -> (3, 5) -> (4, 7) -> (6, 10)
 
 到這里這道題目應(yīng)該已經(jīng)能過(guò)了，不過(guò)還有一種達(dá)到O(1)的優(yōu)化，接下來(lái)的就不是我想出來(lái)的了 =,=
 首先是Betty定理：
 如果無(wú)理數(shù)alpha, beta滿足
 1. alpha, beta > 0
 2. 1/alpha + 1/beta = 1
 那么，序列{[alpha*n]}和{[beta*n]}構(gòu)成自然數(shù)集的一個(gè)分劃，其中[]是取整函數(shù)
 
 這道題對(duì)應(yīng)的alpha和beta分別是(1+sqrt(5))/2,(3+sqrt(5))/2，其實(shí)是一個(gè)黃金分割

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int x, y;
    double alpha = (1.0 + sqrt(5.0)) / 2.0;
    double beta = (3.0 + sqrt(5.0)) / 2.0;
    while (cin >> x >> y) {
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        int n = ceil(y / beta);
        int x1 = alpha * n;
        int y1 = beta * n;
        if (x == x1 && y == y1)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
    return 0;
}