結果

問題 No.7 プライムナンバーゲーム
ユーザー nanae
提出日時 2017-03-02 21:20:49
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 949 bytes
コンパイル時間 843 ms
コンパイル使用メモリ 119,964 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 07:10:58
合計ジャッジ時間 1,551 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio;
import std.string, std.conv, std.array, std.algorithm;
import std.range, std.uni, std.math, std.container;
import core.bitop, std.datetime;

void main(){
    int N = readln.chomp.to!int;
    auto primes = get_primes(N);
    auto dp = new bool[](N + 1);
    dp[0] = dp[1] = true;

    foreach(i ; 2 .. N + 1){
        foreach(p ; primes){
            if(p > i) break;
            if(!dp[i - p]){
                dp[i] = true;
                break;
            }
        }
    }

    //stderr.writeln(dp);

    writeln(dp[N] ? "Win" : "Lose");
}

auto get_primes(int N){
    if(N < 2) throw new Exception("N must be over 1.");
    auto sieve = new bool[](N);
    sieve[] = true;
    sieve[0] = sieve[1] = false;

    foreach(p ; 2 .. N){
        if(p*p > N) break;
        if(!sieve[p]) continue;
        foreach(d ; iota(p*p, N, p)){
            sieve[d] = false;
        }
    }

    return iota(N).filter!(a => sieve[a]).array;
}
0