結果

問題 No.458 異なる素数の和
ユーザー lam6er
提出日時 2025-04-16 15:52:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,269 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 81,540 KB
実行使用メモリ 60,196 KB
最終ジャッジ日時 2025-04-16 15:52:58
合計ジャッジ時間 2,540 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N = int(sys.stdin.readline().strip())
    
    if N < 2:
        print(-1)
        return
    
    # Sieve of Eratosthenes to generate primes up to N
    sieve_size = N
    is_prime = [True] * (sieve_size + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(sieve_size**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, sieve_size+1, i):
                is_prime[j] = False
    primes = [i for i, prime in enumerate(is_prime) if prime]
    
    selected = []
    sum_selected = 0
    k = 0
    # Greedily select primes
    for p in primes:
        if sum_selected + p > N:
            break
        selected.append(p)
        sum_selected += p
        k += 1
    
    if sum_selected == N:
        print(k)
        return
    
    # Check if we can adjust by replacing one prime
    def check_possible(selected_primes, d):
        s = set(selected_primes)
        for p in selected_primes:
            candidate = p + d
            if candidate > sieve_size:
                # Need to check if candidate is prime, but sieve is up to N
                # So candidate might be beyond sieve, but in our problem, candidate can't exceed N + (some prime)
                # However, since d = N - sum_selected, and sum_selected is sum of primes up to selected[-1]
                # sum_selected + next_prime > N, so next_prime > d
                # So candidate = p + d < p + next_prime. But since p is in selected_primes, which are all <= selected[-1]
                # and next_prime is the next prime after selected[-1], candidate could be up to selected[-1] + d
                # However, d = N - sum_selected, and sum_selected + next_prime > N => next_prime > d
                # So candidate = p + d <= selected[-1] + d < selected[-1] + next_prime
                # But since selected[-1] < next_prime, candidate < next_prime + next_prime = 2*next_prime
                # But since next_prime could be larger than N, we can't check via sieve. So for this problem, since sieve is up to N, we can't check candidates beyond N.
                # However, in our problem, d = N - sum_selected, and sum_selected is sum of primes up to selected[-1]
                # sum_selected + next_prime > N => next_prime > d
                # candidate = p + d <= selected[-1] + d = selected[-1] + (N - sum_selected)
                # sum_selected = sum of selected_primes, which includes selected[-1]
                # So selected[-1] <= sum_selected
                # So candidate <= sum_selected + (N - sum_selected) = N
                # Therefore, sieve up to N is sufficient
                pass
            if candidate <= sieve_size and is_prime[candidate] and candidate not in s:
                return True
        return False
    
    d = N - sum_selected
    if check_possible(selected, d):
        print(k)
        return
    
    # Try reducing the number of primes selected
    while k > 0:
        # Remove the last prime
        last_p = selected.pop()
        sum_selected -= last_p
        k -= 1
        d = N - sum_selected
        if d <= 0:
            continue
        if check_possible(selected, d):
            print(k)
            return
    
    print(-1)

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