結果

問題 No.7 プライムナンバーゲーム
ユーザー tshigtshig
提出日時 2016-08-24 17:35:37
言語 Rust
(1.77.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,832 bytes
コンパイル時間 1,315 ms
コンパイル使用メモリ 174,200 KB
実行使用メモリ 6,696 KB
最終ジャッジ日時 2024-04-09 04:02:08
合計ジャッジ時間 1,781 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,564 KB
testcase_01 AC 1 ms
6,688 KB
testcase_02 AC 1 ms
6,688 KB
testcase_03 AC 1 ms
6,692 KB
testcase_04 AC 1 ms
6,688 KB
testcase_05 AC 1 ms
6,696 KB
testcase_06 AC 1 ms
6,696 KB
testcase_07 AC 1 ms
6,692 KB
testcase_08 AC 0 ms
6,692 KB
testcase_09 AC 1 ms
6,688 KB
testcase_10 AC 1 ms
6,692 KB
testcase_11 AC 1 ms
6,692 KB
testcase_12 AC 4 ms
6,688 KB
testcase_13 AC 1 ms
6,692 KB
testcase_14 AC 2 ms
6,692 KB
testcase_15 AC 2 ms
6,696 KB
testcase_16 AC 3 ms
6,692 KB
権限があれば一括ダウンロードができます

ソースコード

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 {
    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