Python程序：寻找划船游戏获胜者

假设我们有一个高度数组height。有n座不同高度的塔。Amal和Bimal正在玩一个游戏。游戏规则如下：

  • Amal总是先走

  • 在每次移动中，当前玩家选择一座高度为X的塔，将其拆分成Y座高度均为Z的塔。[Y*Z = X; X和Y > 1]

  • 无法移动者输掉游戏

我们需要找到获胜者的名字。

所以，如果输入类似height = [3,1,2]，则输出将是Bimal，因为初始高度为{3,1,2}。如果Amal将高度为2的塔拆分成两座高度为1的塔，则新的高度数组将为{3,1,1,1}，Bimal可以将高度为3的塔拆分成三座高度为1的塔，因此Amal无法移动，所以Bimal获胜。

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

  • 定义一个函数util()。这将采用limit参数，初始limit值为10^3+5
  • result := 一个大小为limit的数组，并用0填充
  • 对于范围在2到limit-1的i：
    • s := 一个新的集合
    • 对于范围在1到i的平方根向下取整的j：
      • d := i/j的商，r := i/j的余数
      • 如果r等于0，则：
        • 如果j是奇数，则：
          • 将result[d]插入s
        • 如果d是奇数，则：
          • 将result[j]插入s
    • j := 0
    • 当j存在于s中时：
      • j := j + 1
      • result[i] := j
  • 返回result
  • g := util()
  • 从主方法中执行以下操作：
  • r := 0
  • 对于height中的每个i：
    • r := r XOR g[i]
  • 如果r不为零，则：
    • 返回"Amal"
  • 否则：
    • 返回"Bimal"

示例

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

Open Compiler
def util(limit=10**3+5):
   result = [0] * limit

   for i in range(2, limit):
      s = set()
      for j in range(1, int(i**0.5)+1):
         d, r = divmod(i, j)

         if r == 0:
            if j & 1:
               s.add(result[d])
            if d & 1:
               s.add(result[j])

      j = 0
      while j in s: j += 1
      result[i] = j

   return result

g = util()

def solve(height):
   r = 0

   for i in height:
      r ^= g[i]

   if r:
      return "Amal"
   else:
      return "Bimal"

height = [3,1,2]
print(solve(height))

输入

[3,1,2]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

Bimal

更新于：2021年10月23日

295次浏览

启动您的职业生涯

完成课程后获得认证

开始学习
广告