結果

問題 No.7 プライムナンバーゲーム
ユーザー packet0packet0
提出日時 2015-12-24 18:05:53
言語 Rust
(1.77.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 1,424 bytes
コンパイル時間 658 ms
コンパイル使用メモリ 163,484 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-09 03:53:14
合計ジャッジ時間 1,421 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

use std::io;
use std::iter;

fn main() {
    let stdin = io::stdin();
    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    let n: usize = line.trim().parse().unwrap();

    let prime = list_prime(n as usize);

    let len = n - 1; // for [2, n]
    let mut can_win: Vec<bool> = Vec::with_capacity(len);

    for i in 0..len {
        let num = i + 2;
        let mut win = false;
        for &p in &prime {
            if p + 1 >= num {//rem = 0 or 1 or minus
                break;
            }
            let rem = num - p;
            if !can_win[rem - 2] {
                win = true;
                break;
            }
        }
        can_win.push(win);
    }
    println!("{}", if *can_win.last().unwrap() {
        "Win"
    } else {
        "Lose"
    });
}

fn list_prime(roof: usize) -> Vec<usize> {
    if roof < 2 {
        return Vec::with_capacity(0);
    }
    let len = roof - 1;
    let mut table_remain: Vec<bool> = iter::repeat(true).take(len).collect();
    let mut prime = Vec::with_capacity(len);

    for i in 0..len {
        if table_remain[i] {
            let num = i + 2;
            prime.push(num);
            let mut j = i;
            // check to prevent arithmetic overflow
            while j < std::usize::MAX - num && j + num < len {
                j = j + num;
                table_remain[j] = false;
            }
        }
    }

    return prime;
}
0