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(s: &str) -> T { s.parse().ok().expect("parse error.") } #[allow(dead_code)] fn get_vec() -> Vec { (&get_line()).split(' ').map(cast::).collect() } /* ---------- ここまでテンプレ ---------- */ // エラトステネスの篩で素数表を生成 fn make_primes(n: usize) -> Vec { let mut primes: Vec = Vec::new(); let mut is_prime: Vec = vec![true; n+1]; is_prime[1] = false; for i in 2..n+1 { if !is_prime[i] {continue}; primes.push(i); for j in 2..n+1 { if i * j > n {break;} is_prime[i * j] = false; } } primes } // 自分の番がmで回ってきたときに勝てるならtrue fn game(m: usize, dp: &mut Vec>, primes: &Vec) -> bool { if m < 2 { // 1手前にすでに相手が負けている return true; } if dp[m] != None { // メモを利用 return dp[m].unwrap(); } let mut ret = false; for &p in primes { if m < p {break;} // dp[m - p]=falseならm-pにすれば勝てる ret |= !game(m - p, dp, primes); } dp[m] = Some(ret); ret } fn main() { let n: usize = cast(&get_line()); let primes = make_primes(n); let mut dp: Vec> = vec![None; n + 1]; // gameの返り値をメモ println!("{}", if game(n, &mut dp, &primes) {"Win"} else {"Lose"} ); }