結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:18:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 80 ms / 5,000 ms
コード長 987 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 76,672 KB
最終ジャッジ日時 2025-03-20 21:19:20
合計ジャッジ時間 2,272 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    N = int(input().strip())
    max_n = 10000

    # Sieve of Eratosthenes to generate primes up to max_n
    sieve = [True] * (max_n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(max_n**0.5) + 1):
        if sieve[i]:
            sieve[i*i : max_n + 1 : i] = [False] * len(sieve[i*i : max_n + 1 : i])
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]

    # DP array where dp[i] is True if the current player can win with number i
    dp = [False] * (max_n + 1)

    for i in range(2, max_n + 1):
        max_p = i - 2
        if max_p < 2:
            continue  # No primes <= max_p, so skip (dp[i] remains False)
        idx = bisect.bisect_right(primes, max_p)
        for p in primes[:idx]:
            prev = i - p
            if not dp[prev]:
                dp[i] = True
                break  # Found a winning move, no need to check others

    print("Win" if dp[N] else "Lose")

if __name__ == "__main__":
    main()
0