結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー packet0
提出日時 2015-12-24 18:13:46
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,391 bytes
コンパイル時間 13,120 ms
コンパイル使用メモリ 382,984 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-01 15:39:04
合計ジャッジ時間 12,153 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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> = iter::repeat(false).take(len).collect();

    for i in 0..len {
        let num = i + 2;
        for &p in &prime {
            if p + 1 >= num {//rem = 0 or 1 or minus
                break;
            }
            let rem = num - p;
            if !can_win[rem - 2] {
                can_win[i] = true;
                break;
            }
        }
    }
    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