Pythonでセット要素除去ゲームの勝者を見つけるためのプログラム

最初のn個の自然数{1..n}のセットがあるとします。アマルとビマルがゲームをしています。ゲームのルールは以下のとおりです

• アマルは常に最初にプレイします

• 各移動中に、現在のプレーヤーはセットから素数pを選択します。次に、プレーヤーはpとそのすべての倍数をセットから削除します。

• 動きのない人は誰でもゲームに負けます。nがあれば、勝者の名前を見つける必要があります。

したがって、入力がn =5の場合、初期セットは{1,2,3,4,5}であるため、出力はAmalになります。ここで、Amalが数値p =2を選択し、セットから2、4を削除すると、現在のセットは{1,3,5}になり、2つの素数が残っているため、Bimalはそれらのいずれかを選択できますが、残りの要素はありません。削除し、最後にアマルは別の素数を削除してゲームに勝ちます。

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

• primes：=サイズ100000の配列、最初はすべて0
• ふるい：=サイズ100000の配列、最初はすべて0
• 2〜99999の範囲のiの場合は、
  • sieve [i]が0と同じ場合、
    • primes [i]：=primes [i-1] +1
    • iから100000の範囲のjについては、各ステップでiずつ更新します。
      • ふるい[j]：=i
  • それ以外の場合、
    • primes [i]：=primes [i-1]
• メインの方法から次のようにします-
• primes [n]が奇数の場合は「Bimal」を返し、それ以外の場合は「Amal」を返します

例

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

primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
   if sieve[i] == 0:
      primes[i] = primes[i-1]+1

      for j in range(i, 100001, i):
         sieve[j] = i
   else:
      primes[i] = primes[i-1]

def solve(n):
   return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))

入力

5

出力

Amal