結果
問題 | No.153 石の山 |
ユーザー |
![]() |
提出日時 | 2019-02-07 23:34:58 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 5,000 ms |
コード長 | 837 bytes |
コンパイル時間 | 12,898 ms |
コンパイル使用メモリ | 402,300 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 07:25:08 |
合計ジャッジ時間 | 14,297 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#[allow(unused_imports)]use std::cmp::*;#[allow(unused_imports)]use std::collections::*;fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}fn grundy(n: usize, mem: &mut Vec<i32>) -> i32 {if mem[n] != -1 {return mem[n];}let mut s = HashSet::new();s.insert(grundy(n / 2, mem) ^ grundy(n - n / 2, mem));s.insert(grundy(n / 3, mem) ^ grundy((1 + n) / 3, mem) ^ grundy((2 + n) / 3, mem));let mut res = 0;while s.contains(&res) {res += 1;}mem[n] = res;res}fn main() {let n: usize = read();let mut mem = vec![-1; n + 1];mem[0] = 0;mem[1] = 0;if grundy(n, &mut mem) == 0 {println!("B");} else {println!("A");}}