Python程序：求起始玩家必胜的初始走法数量

假设Amal和Bimal正在玩一个游戏。他们有n个容器，每个容器里都有一些巧克力。这些容器编号从1到N，其中第i个容器有count[i]块巧克力。游戏的规则如下：第一个玩家选择一个容器并从中取走一块或多块巧克力。然后第二个玩家选择一个非空容器并从中取走一块或多块巧克力，以此类推，轮流进行。当其中一个玩家无法再取走任何巧克力时，他就输了。如果Amal先走，我们必须找出Amal有多少种第一种走法，可以保证他总是赢。

例如，如果输入是count = [2, 3]，则输出为1，因为容器最初的状态是[2, 3]。他们可以这样玩：

• Amal从第二个容器中取一块巧克力，当前状态为[2, 2]
• Bimal从第一个容器中取一块巧克力，当前状态为[1, 2]
• Amal从第二个容器中取一块巧克力，当前状态为[1, 1]
• Bimal从第一个容器中取一块巧克力，当前状态为[0, 1]

为了解决这个问题，我们将遵循以下步骤：

• tmp := 0
• 对count中的每个c，执行：
  • tmp := tmp XOR c
• 如果tmp为零，则
  • 返回0
• 否则，
  • moves := 0
  • 对count中的每个c，执行：
    • moves := moves + (当(tmp XOR c) < c时为1，否则为0)
  • 返回moves

示例

让我们看看下面的实现来更好地理解：

def solve(count):
   tmp = 0
   for c in count:
      tmp ^= c

   if not tmp:
      return 0
   else:
      moves = 0
      for c in count:
         moves += (tmp^c) < c
      return moves

count = [2, 3]
print(solve(count))

输入

[2, 3]

输出

1

Arnab Chakraborty

更新于：2021年10月23日

242 次浏览

开启你的职业生涯

完成课程获得认证

开始学习