Pythonで可能になるまで、配列内の要素のペアワイズ差を追加して、勝者を見つけます

正の整数の配列Aがあり、要素が一意であるとすると、2人のプレーヤーPとQがゲームをプレイしています。各移動で、1人のプレーヤーが配列から2つの数字aとbを選び、| a –b|の場合その後、プレーヤーはこの番号を配列に追加します。プレイヤーが移動できない場合、ゲームに負けます。プレーヤーPが常にゲームを開始する場合は、ゲームの勝者を見つける必要があります。

したがって、入力がA =[8,9,10]の場合、出力はPになります。

これを解決するには、次の手順に従います-

• n：=arrのサイズ

• g：=arr [0]、max_val：=arr [0]

• 1からnの範囲のiの場合、実行します

  • g：=gcd（g、arr [i]）

  • max_val：=max_valの最大値、arr [i]

• 合計：=（max_val / g）-n

• 合計が奇数の場合、

  • 'P'を返す

• 'Q'を返す

例

理解を深めるために、次の実装を見てみましょう-

from math import gcd
def who_is_the_winner(arr) :
   n = len(arr)
   g = arr[0]
   max_val = arr[0]
   for i in range(1, n) :
      g = gcd(g, arr[i])
      max_val = max(max_val, arr[i])
   total = (max_val / g) - n
   if (total % 2 == 1) :
      return 'P'
   return 'Q'

arr = [8,9,10]
print(who_is_the_winner(arr))

入力

[8,9,10]

出力

P