use std::io::{stdin, Read, StdinLock}; use std::str::FromStr; struct Input { n: usize, } fn read_input(cin_lock: &mut StdinLock) -> Input { let n = next_token(cin_lock); Input { n } } fn generate_prime_numbers(n: usize) -> Vec { let mut primes = vec![true; n + 1]; primes[0] = false; primes[1] = false; let limit = (n as f64).sqrt() as usize + 1; for i in 2..limit { if !primes[i] { continue; } for j in 2..n { if i * j > n { break; } primes[i * j] = false; } } primes .iter() .enumerate() .filter(|(_, v)| **v) .map(|(i, _)| i) .collect() } #[derive(Clone, Copy, PartialEq, Debug)] enum GameResult { Win, Lose, Unkown, } fn solve(input: Input) -> GameResult { let prime_numbers = generate_prime_numbers(input.n); let mut game_results = vec![GameResult::Unkown; input.n.max(1) + 1]; game_results[0] = GameResult::Win; game_results[1] = GameResult::Win; for curr_move in 0..input.n { for prime_number in 0..prime_numbers.len() { if curr_move + prime_numbers[prime_number] > input.n { continue; } let next_move = curr_move + prime_numbers[prime_number]; game_results[next_move] = match game_results[next_move] { GameResult::Win => GameResult::Win, _ => match game_results[curr_move] { GameResult::Lose => GameResult::Win, GameResult::Win => GameResult::Lose, GameResult::Unkown => panic!("result is unknown"), }, }; } if game_results[input.n] == GameResult::Win { return game_results[input.n]; } } game_results[input.n] } fn main() { let cin = stdin(); let mut cin_lock = cin.lock(); let input = read_input(&mut cin_lock); println!( "{}", match solve(input) { GameResult::Win => "Win", GameResult::Lose => "Lose", GameResult::Unkown => panic!("result is unkown"), } ); } #[cfg(test)] mod tests { use super::*; #[test] fn test_solve_01() { assert_eq!(solve(Input { n: 2 }), GameResult::Lose); assert_eq!(solve(Input { n: 5 }), GameResult::Win); assert_eq!(solve(Input { n: 12 }), GameResult::Lose); } } fn next_token(cin_lock: &mut StdinLock) -> T { cin_lock .by_ref() .bytes() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::() .parse::() .ok() .unwrap() }