Posted on 2007-10-31 18:11
ZelluX 閱讀(1764)
評論(2) 編輯 收藏 所屬分類:
Algorithm
問題：
有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。
碰到這道題時我的思路：
設(shè)集合A, B分別為先手能贏和后手能贏的二元無序?qū)?x,y)的集合
先從最基礎(chǔ)的開始考慮，(n,0) (n,n) 屬于A，因為這樣的情況先手肯定能贏（n為正整數(shù)，下同）
如果存在(a,b)，對于一切n，(a-n,b-n)均屬于A，則(a,b)屬于B
很容易找到一個(2,1)，這是后手肯定能贏的情況
接下來從先手的角度分析，如果他能在移動石子后留給對手(2,1)個石子，那么他就能贏，于是
(2+n,1) (2+n,1+n) (2,1+n) 均屬于 A
找出一個不屬于A的最小對，(5,3)， 這個元素肯定屬于B集合，因為從中任意取出元素后的結(jié)果肯定屬于A集合
相應(yīng)的，(5+n, 3) (5, 3+n), (5+n, 3+n) 均屬于A
這時發(fā)現(xiàn)，B集合相對A集合元素少很多，只要找出B集合中元素的特征，就能解決這個問題。
一旦B中包含(x,y)對，A中就會相應(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), 對于一切(p, q)屬于S }
則把(a, a+gap)加入B中，其中g(shù)ap是當(dāng)前S中所有對之差的最小值+1
構(gòu)造出的序列為
(1,2) -> (3, 5) -> (4, 7) -> (6, 10)
到這里這道題目應(yīng)該已經(jīng)能過了，不過還有一種達到O(1)的優(yōu)化，接下來的就不是我想出來的了 =,=
首先是Betty定理：
如果無理數(shù)alpha, beta滿足
1. alpha, beta > 0
2. 1/alpha + 1/beta = 1
那么，序列{[alpha*n]}和{[beta*n]}構(gòu)成自然數(shù)集的一個分劃，其中[]是取整函數(shù)
這道題對應(yīng)的alpha和beta分別是(1+sqrt(5))/2,(3+sqrt(5))/2，其實是一個黃金分割
#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;
}