結果
問題 |
No.7 プライムナンバーゲーム
|
ユーザー |
|
提出日時 | 2020-06-21 12:21:43 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,297 bytes |
コンパイル時間 | 101 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 17,152 KB |
最終ジャッジ日時 | 2024-07-03 17:56:08 |
合計ジャッジ時間 | 20,046 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 8 TLE * 2 |
ソースコード
import math def calc_prime(n): is_prime = [True] * n prime_nums = set() is_prime[0], is_prime[1] = False, False for i in range(n): if is_prime[i]: for j in range(i * 2, n, i): is_prime[j] = False prime_nums.add(i) return prime_nums def dfs(n, turn): # print(n, turn) if memo[n][turn] != -1: return memo[n][turn] if n <= 1: return 1 ^ turn # 1なら勝利,0なら敗北 under_n_primes = [p for p in primes if p <= n][::-1] # print(" ", under_n_primes) # プレイヤーごとの処理 if turn == 0: for p in under_n_primes: if dfs(n - p, 1) == 1: # ORノード 1つでも勝ちならOK memo[n-p][turn] = 1 return 1 # 1つも勝ちがない memo[n-p][turn] = 0 return 0 else: for p in under_n_primes: if dfs(n - p, 0) == 0: # ANDノード 1つの負け筋でダメ memo[n-p][turn] = 0 return 0 # 逆 memo[n-p][turn] = 1 return 1 N = int(input()) primes = calc_prime(N + 1) memo = [[-1] * 2 for i in range(N+1)] # 0=先手,1=後手 cond = dfs(N, 0) print("Win" if cond else "Lose")