結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー nanae
提出日時 2017-03-02 21:04:23
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 865 bytes
コンパイル時間 826 ms
コンパイル使用メモリ 118,316 KB
実行使用メモリ 9,500 KB
最終ジャッジ日時 2024-06-12 07:10:56
合計ジャッジ時間 7,548 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

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);
    //primes.array.writeln;
    auto judge = game(N, primes.array);
    writeln(judge ? "Win" : "Lose");
}

bool game(int N, int[] primes){
    bool ret = false;
    if(N <= 1) return true;

    foreach(i ; primes){
        if(i > N) break;
        ret |= !game(N - i, primes);
    }

    return ret;
}

auto get_primes(int N){
    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]);
}
0