[ALG]POJ1067解题报告

来源:转载

[Wythoff's game]

初始:两堆物品
动作:从一堆中取任意数量或从两堆中取相同数量
结束:拿走最后一个物品的胜利

[等价模型]
1/4无限的象棋盘上将queen移到角落位置

[贝蒂定理(Betti theorem)]
设a、b是正无理数且 1/a +1/b =1。记P={ [na] | n为任意的正整数},Q={ [nb] | n 为任意的正整数},([x]'指的是取x的整数部分)则P与Q是Z+的一个划分,即P∩Q为空集且P∪Q为正整数集合Z+。

[非完备解答]
对称性只考虑x<y, 若(x,y)为p位置则显然(x+k,y),(x+k,y+k),(x,y+k){k>0} 都为必胜点
一个p位置序列:(0,0) (1,2) (3,5)
所以p位置(x,y), x,y差越来越大,且都是前面未出现过的。
构造这样一个划分:
 1. 1/a+1/b=1; 
 2. p=[na],q=[nb] {(p,q)为p位置}
 3. [na]-[nb]=n,
    => a=1+b,
    => b=(1+√5)/2
 4. 若φ = (1+√5)/2,则p位置为([φ2 n], [φ n])

[code]

#include <cstdio>
#include <cmath>
#define SITA ((1.0 + sqrt(5.0)) / 2.0)
using namespace std;
int main()
{
int a, b, temp;
while(scanf("%d %d",&a,&b) == 2)
{
if(a > b)
{
temp = b;
b = a;
a = temp;
}
if(floor((b - a) * SITA) == a)
{
printf("0/n");
}
else
{
printf("1/n");
}
}
return 0;
}


分享给朋友:
您可能感兴趣的文章:
随机阅读: