結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2020-10-08 15:37:24 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 5,000 ms |
コード長 | 1,793 bytes |
コンパイル時間 | 13,232 ms |
コンパイル使用メモリ | 402,324 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-01 09:57:10 |
合計ジャッジ時間 | 14,175 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
use std::collections::VecDeque; 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 solve(input: Input) -> i32 { let mut deque: VecDeque<u32> = VecDeque::new(); let mut check_points = vec![-1; input.n + 1]; deque.push_back(1); check_points[0] = 0; check_points[1] = 1; while let Some(n) = deque.pop_front() { let bc = n.count_ones(); if check_points.len() > (n + bc) as usize && check_points[(n + bc) as usize] < 0 { check_points[(n + bc) as usize] = check_points[n as usize] + 1; deque.push_back(n + bc); } if n >= bc && check_points[(n - bc) as usize] < 0 { check_points[(n - bc) as usize] = check_points[n as usize] + 1; deque.push_back(n - bc); } } return check_points[input.n]; } #[cfg(test)] mod tests { use super::*; #[test] fn test_solve() { assert_eq!(solve(Input { n: 1 }), 1); assert_eq!(solve(Input { n: 2 }), 2); assert_eq!(solve(Input { n: 3 }), 3); assert_eq!(solve(Input { n: 4 }), -1); assert_eq!(solve(Input { n: 5 }), 4); assert_eq!(solve(Input { n: 11 }), 9); } } fn next_token<T: FromStr>(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::<String>() .parse::<T>() .ok() .unwrap() } fn main() { let cin = stdin(); let mut cin_lock = cin.lock(); let input = read_input(&mut cin_lock); println!("{}", solve(input)); }