use std::collections::HashMap; use proconio::marker::Chars; fn main() { proconio::input! { n: u64, } let mut memo = HashMap::new(); for n in 2..=10000 { winlose(n, &mut memo); } if winlose(n, &mut memo) { println!("Win"); } else { println!("Lose"); } } fn proc(n: u64) -> u64 { (n / 3 + n / 5) * 2 } const PRIME_NUM: [u64; 1229] = { let mut tbl = [0; 1229]; let mut i = 0; let mut p = 0; while p < PRIME.len() as u64 { if PRIME[p as usize] { tbl[i] = p; i += 1; } p += 1; } tbl }; const PRIME: [bool; 10001] = create_prime(); const fn create_prime() -> [bool; N] { let mut table = [true; N]; table[0] = false; table[1] = false; let mut i = 2; while i < N { if table[i] { let mut j = i * 2; while j < N { table[j] = false; j += i; } } i += 1; } table } fn winlose(n: u64, memo: &mut HashMap) -> bool { if n < 2 { return true; } if let Some(&memo) = memo.get(&n) { return memo; } let result = PRIME_NUM .iter() .copied() .take_while(|&x| x < n) .any(|x| !winlose(n - x, memo)); memo.insert(n, result); result } #[cfg(test)] mod test { use super::*; #[test] fn test() {} }