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