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"

示例

讓我們看看下面的實現以更好地理解：

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]

輸出

Bimal

更新於：2021年10月23日

295次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始學習
廣告