AmalがPythonでストーンゲームに勝つことができるかどうかをチェックするプログラム

AmalとBimalの2人のプレーヤーがいて、彼らがゲームをプレイしていて、Amalが最初に開始するとします。最初は、山の中にn個の異なる石があります。各プレイヤーのターンで、彼は山から任意の平方数（ゼロ以外）の石を取り除くことからなる動きをします。また、1人のプレーヤーが移動できない場合、そのプレーヤーはゲームに負けます。したがって、nがある場合、Amalがゲームに勝つことができるかどうかを確認する必要があります。

したがって、入力がn =21の場合、出力はTrueになります。これは、最初にAmalが16を取り、次にBimalが4を取り、次にAmalが1を取り、ゲームに勝つためです。

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

• 四角：=新しいリスト

• 正方形：=1

• 増加：=3

• 正方形<=n、実行

  • 正方形の端に正方形を挿入します

  • 正方形：=正方形+増加

  • 増加：=増加+ 2

• 正方形の端に正方形を挿入します

• dp：=サイズの空白リスト（n + 1）

• dp [0]：=False

• 1からnの範囲のkについては、次のようにします

  • s：=0

  • dp [k]：=False

  • squares [s] <=kおよびdp[k]が空の場合、実行

    • dp [k --squares [s]]が空の場合、

      • dp [k]：=True

    • s：=s + 1

• dpの最後の要素を返す

例

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

def solve(n):
   squares = []
   square = 1
   increase = 3
   while square <= n:
      squares.append(square)
      square += increase
      increase += 2
   squares.append(square)

   dp = [None] * (n + 1)
   dp[0] = False
   for k in range(1, n + 1):
      s = 0
      dp[k] = False
      while squares[s] <= k and not dp[k]:
         if not dp[k - squares[s]]:
            dp[k] = True
         s += 1
   return dp[-1]

n = 21
print(solve(n))

入力

21

出力

True