01067: 取石子游戏

math, game theory, http://cs101.openjudge.cn/practice/01067/

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

输入

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

输出

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

样例输入

2 1
8 4
4 7

样例输出

0
1
0

来源: NOI

python

import math

def wythoff(a, b):
    if a > b:
        a, b = b, a  # Make sure a <= b.
    k = b - a
    ak = k * (math.sqrt(5) + 1) / 2  # ak is the k-th element in the Beatty sequence.
    return 1 if a != int(ak) else 0

while True:
    try:
        a, b = map(int, input().split())
    except:
        break

    ans = wythoff(a, b)

    print(ans)

【翟宇晟-25数院】此题题解没有任何解释，所以我想分享一个较为自然的想法：

对任意非负整数m,n，定义f(m,n)：若m,n情形下先手必胜，则f(m,n)=1；否则，f(m,n)=0。观察可知：m=n或m*n=0（除了m=n=0）时，f(m,n)=1。进一步观察，由取法一得：对固定的m，若f(m,n1)=0，则对任意n>n1，f(m,n)=1（第一步从n中取n-n1个），由取法二得：对固定的m,n，若f(m,n)=0，则对任意正整数k，f(m+k,n+k)=0（第一步各取k个）。

由上，不难发现并证明：对0<m<n，f(m,n)=0等价于(m,n)在此集合中：{(1,2),(3,5),(4,7)……}，此集合由归纳定义：(a1,b1)=(1,2)在集合中，假设(a1,a2),……(an,bn)在集合中，则a(n+1)为不在{ak},{bk}（k=1,2……n）中出现的最小正整数，b(n+1)为a(n+1)加上“不在{ak-bk}（k=1,2……n）中出现的最小正整数”。简单来说，<1>.{an}，{bn}构成正整数的一个划分（且这个划分比较均匀），<2>.an-bn=n。

我们想到贝亚蒂定理（Beatty's theorem）：若正无理数c,d,使得1/c + 1/d = 1，则{[cn]}, {[dn]}（n=1,2,3……）构成正整数集的一个划分，这是一个很好的想法（能直接满足<1>）。尝试一下：待定c,d,令an=[cn]，bn=[dn]，想让它满足<2>,即[cn]-[dn]=n，令n趋向于正无穷，得c-d=1，联立解得c=(3+sqrt(5))/2，d= (1+sqrt(5))/2，出现了这么美妙的数字（与黄金分割率相关），我们有理由相信这么做是有前途的，后面通过归纳证明，不难得到，{an}，{bn}就是{[cn]}，{[dn]}。

【马铉钦25化院】容易知道，态 $(i, j)$ 的子状态有 $(a, j), (i, b), (i - x, j - x)$ ,其中 $(0 <= a < i, 0 <= b < j, 0 < x <= m i n (i, j))$ 。这些态中只要有一个是必败态，那么态 $(i, j)$ 就是必胜态。利用这个方法，找到必败态的前几项（过程可以参见如Beatty序列与Wythoff博弈 - emofunc - 博客园，这个网站也提供了严谨的数学证明）： $(0, 0), (2, 1), (5, 3), (7, 4), (10, 6), (13, 8), (15, 9), (18, 11), (20, 12), (23, 14), (26, 16), (28, 17), (31, 19), (34, 21)$ （以及和它们对称的态）列举到这里，聪明的你想必应该发现：在这些态中，Fibonacci数列的相邻项总是成对出现的： $(2, 1), (5, 3), (13, 8), (34, 21)$ ,那我们再把中间那些态和在它前面和它最靠近的由Fibonacci数组成的态做差，如 $(15, 9) - (13, 8) = (2, 1), (18, 11) - (13, 8) = (5, 3)$ ... 我们惊喜地发现，这样处理得到的态仍然是必败态，而且最后一定会得到由Fibonacci数组成的必败态；如果可以减自身的话，最后一定会得到(0,0)。再考虑一下不要将必胜误判为必败，我们有下面的可以AC的代码：

python

import bisect
li1=[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170]
li=[(1,2),(3,5),(8,13),(21,34),(55,89),(144,233),(377,610),(987,1597),(2584,4181),(6765,10946),(17711,28657),(46368,75025),(121393,196418),(317811,514229),(832040,1346269),(2178309,3524578),(5702887,9227465),(14930352,24157817),(39088169,63245986),(102334155,165580141),(267914296,433494437)]

def jug(a,b):
    ind1a,ind1b=bisect.bisect(li1,a),bisect.bisect(li1,b)
    if li1[ind1a-1]==a and li1[ind1b-1]==b:
        return int(not(ind1a==ind1b-1 and ind1a%2==1))
    elif li1[ind1a-1]==a or li1[ind1b-1]==b:
        return 1
    elif a==b==0:
        return 0
    elif a<=0 or b<=0:
        return 1
    
    
    return jug(a-li1[ind1a-1],b-li1[ind1b-1])
try:
    while True:
        a,b=map(int,input().split())
        
        a,b=min(a,b),max(a,b)
        print(jug(a,b))
                
except EOFError:
    pass

3 2和8 5两组，答案都是1。

【陈子良 25物理学院】颠覆世界观级别的博弈题，非数院不能做。之前也发到微信群里让大家品鉴过了。

python

import math
while True:
    try:
        a,b=map(int,input().split())
    except EOFError:
        break
    if a>b:
        a,b=b,a
    k=b-a
    if a==int(k*(math.sqrt(5)+1)/2):
        print(0)
    else:
        print(1)

01067: 取石子游戏 ​

01067: 取石子游戏