Python：每日一题之取球博弈

题目描述

两个人玩取球的游戏。

一共有 N 个球，每人轮流取球，每次可取集合 n1,n2,n3中的任何一个数目。

如果无法继续取球，则游戏结束。

此时，持有奇数个球的一方获胜。

如果两人都是奇数，则为平局。

假设双方都采用最聪明的取法，

第一个取球的人一定能赢吗？

试编程解决这个问题。

输入描述

输入格式：

第一行 3 个正整数 n1,n2,n3 (0<n1,n2,n3<100)，空格分开，表示每次可取的数目。

第二行 5 个正整数 x1,x2,⋯,x5 (0<xi<1000)，空格分开，表示 5 局的初始球数。

输出描述

输出一行 5 个字符，空格分开。分别表示每局先取球的人能否获胜。

能获胜则输出 +，次之，如有办法逼平对手，输出 0，无论如何都会输，则输出 -。

输入输出样例

示例

输入

1 2 3
1 2 3 4 5

输出

+ 0 + 0 -

参考代码：

import sys
sys.setrecursionlimit(1000000)
n=list(map(int,input().split()))
n.sort()
x=list(map(int,input().split()))
vis={}
def cal(num,t1,t2):
    if num<n[0]:
        if t1 and ~t2:return +
        elif ~t1 and t2:return -
        else:return 0
    if (num,t1,t2) in vis:return vis[(num,t1,t2)]
    tag=0
    for i in range(3):
        if num>=n[i]:
            ans=cal(num-n[i],t2,(~t1 if n[i]%2 else t1))    
            if ans==-:
                vis[(num,t1,t2)]=+
                return +
            if ans==0:tag=1
    if tag:
        vis[(num,t1,t2)]=0
        return 0
    vis[(num,t1,t2)]=-
    return -
for i in range(5):
    print(cal(x[i],0,0),end=" ")