結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2018-09-03 19:10:16 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 1,404 bytes |
コンパイル時間 | 12,519 ms |
コンパイル使用メモリ | 378,352 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 16:13:58 |
合計ジャッジ時間 | 12,274 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
use std::io::*; use std::str::FromStr; #[allow(dead_code)] fn get_line() -> String { let stdin = stdin(); let mut line = String::new(); stdin.lock().read_line(&mut line).expect("io error."); line.trim().to_string() } #[allow(dead_code)] fn cast<T: FromStr>(s: &str) -> T { s.parse().ok().expect("parse error.") } #[allow(dead_code)] fn get_vec<T: FromStr>() -> Vec<T> { (&get_line()).split(' ').map(cast::<T>).collect() } /* ---------- ここまでテンプレ ---------- */ fn main() { // まずはエラトステネスの篩 let mut is_prime: Vec<bool> = vec![true; 10001]; is_prime[1] = false; for i in 2..101 { if !is_prime[i] {continue}; for j in 2..10000 { if i * j > 10000 {break;} is_prime[i * j] = false; } } // filterで素数配列を生成 let primes: Vec<usize> = (1..10001) .filter(|x| is_prime[*x]) .collect(); // ここからが本編 let n: usize = cast(&get_line()); let mut dp: Vec<bool> = vec![true; n + 1]; // 自分の番がmで回ってきたときに勝てるならtrue for m in 2..n+1{ let mut ret = false; for p in &primes { if m > *p { ret |= !dp[m - *p]; } } dp[m] = ret; } println!("{}", if dp[n] {"Win"} else {"Lose"}); }