Wythoff Game(hdu2177)

2014-11-24 10:18:12 · 作者: · 浏览: 0

对于某个局势(a,b) ,b>=a
差值k=b-a
对于某个确定的k
有唯一的奇异局势(必败点) (a_k,b_k) 其中a_k=k*(1+sqrt(5))/2 b_k=a_k+k
如果a,b是奇异局势 则输出0
不是的话输出1(通过某种操作可以获胜)

已知a,b
操作分5种
1.a==b
同时减去a 得到0,0

2.a==a_k b>b_k
b -(b-b_k)

3.a==a_k b 同时拿走a_k-a_(b-a_k)
得到 a_(b-a_k) a_(b-a_k) + b-a_k

4.a>a_k b==b_k
从a中拿走 a-a_k

5.a 5.1 a==a_ j (j b-(b-b_ j)
得到 a_ j b_ j
5.2 a==b_ j (j b-(b-a_ j)
得到 b_ j a_ j