結果

問題 No.7 プライムナンバーゲーム
ユーザー gorugo30gorugo30
提出日時 2021-02-25 21:30:34
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 494 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 80,032 KB
最終ジャッジ日時 2024-04-08 21:58:01
合計ジャッジ時間 2,659 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
66,732 KB
testcase_01 AC 56 ms
66,732 KB
testcase_02 RE -
testcase_03 AC 64 ms
71,724 KB
testcase_04 AC 62 ms
69,264 KB
testcase_05 AC 66 ms
69,260 KB
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 65 ms
71,868 KB
testcase_09 RE -
testcase_10 AC 53 ms
66,732 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def isp(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True
P = []
for i in range(2, 10001):
    if isp(i):
        P.append(i)
def canwin(x):
    if x <= 1:
        return 1
    if dp[x] != -1:
        return dp[x]
    ans = 0
    for p in P:
        if p > x:
            break
        ans |= canwin(x - p) ^ 1
    dp[x] = ans
    return ans

N = int(input())
dp = [-1] * (N + 1)
if canwin(N):
    print("Win")
else:
    print("Lose")
0