結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2019-01-31 14:16:46 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,576 ms / 5,000 ms |
コード長 | 1,050 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-10-01 16:18:04 |
合計ジャッジ時間 | 11,478 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
N = int(input()) dq = [-1] * 10010 # 2と3になると負けか確定なので2と3は0とする。 dq[2] = 0 dq[3] = 0 #N以下の素数の抽出 prime = [] def eratos(N): Num = [i for i in range(2 , N + 1)] prime.append(Num[0]) prime_number = prime[0] while prime_number * prime_number < N: Num = [i for i in Num if i % prime_number != 0] prime.append(Num[0]) prime_number = Num[0] Num.remove(prime_number) prime.extend(Num) def grundy(x): s = set() #集合sを作成 for i in reversed(prime): if (x - i >= 2): if(dq[x - i] != -1): s.add(dq[x - i]) else: dq[x - i] = grundy(x - i) s.add(dq[x - i]) #grundy数を集合に入れる #集合sの値を確認して、sにない最小の数値をdq[x]とする。 for i in range(len(prime) + 1): if i not in s: dq[x] = i break return dq[x] eratos(N) if(grundy(N) == 0): print("Lose") else: print("Win")