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

更新於：2021年10月23日

242 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告