結果

問題 No.7 プライムナンバーゲーム
ユーザー tshigtshig
提出日時 2016-08-24 17:35:06
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 1,855 bytes
コンパイル時間 1,520 ms
コンパイル使用メモリ 172,616 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-25 15:06:17
合計ジャッジ時間 2,308 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io;
use std::io::prelude::*;
use std::io::BufReader;

fn calc_primes(n: u32) -> Vec<u32> {
    let mut sieve = vec![true; (n + 1) as usize];
    let max = (n as f64).sqrt() as u32;
    for i in 2..(max + 1) {
        if sieve[i as usize] {
            let mut j = i * 2;
            while j <= n {
                sieve[j as usize] = false;
                j += i;
            }
        }
    }

    let mut primes: Vec<u32> = vec![];
    for (i, &s) in sieve.iter().enumerate().skip(2) {
        if s {
            primes.push(i as u32);
        }
    }

    primes
}

fn calc(args: &Vec<String>) -> bool {
    let n: u32 = args[0].parse().unwrap();

    let mut primes = calc_primes(n);
    primes.reverse();

    let mut memo = vec![None; (n + 1) as usize];

    rec(n, true, &primes, &mut memo)
}

fn rec(n: u32, turn: bool, primes: &Vec<u32>, memo: &mut Vec<Option<bool>>) -> bool {
    println!("{}", n);
    let winner: bool;

    if n == 0 || n == 1 {
        winner = true;
    } else {
        winner = match memo[n as usize] {
            Some(winner) => winner,
            None => rec_call(n, turn, primes, memo)
        }
    }

    memo[n as usize] = Some(winner);
    !(winner ^ turn)
}

fn rec_call(n: u32, turn: bool, primes: &Vec<u32>, memo: &mut Vec<Option<bool>>) -> bool {
    for &p in primes.iter().skip_while(|&&p| p > n) {
        if rec(n - p, !turn, primes, memo) == turn {
            return true;
        }
    }
    false
}

fn run(args: &Vec<String>) -> Vec<String> {
    if calc(args) {
        vec!["Win".to_string()]
    } else {
        vec!["Lose".to_string()]
    }
}

fn main() {
    let args = lines(BufReader::new(io::stdin()));
    for line in run(&args) {
        println!("{}", line);
    }
}

fn lines<R: Read>(reader: BufReader<R>) -> Vec<String> {
    reader.lines().map(|l| l.unwrap()).collect()
}
0