結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2019-10-18 00:37:11 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,096 bytes |
コンパイル時間 | 12,800 ms |
コンパイル使用メモリ | 390,744 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:32:28 |
合計ジャッジ時間 | 14,050 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
use std::io::{self, Read}; use std::collections::{VecDeque, HashSet}; fn read_stdin() -> Vec<String> { let mut buffer = String::new(); io::stdin().read_to_string(&mut buffer).ok(); buffer.trim().split('\n').map(|s| s.to_string()).collect() } fn main() { let n = read_stdin()[0].parse::<usize>().unwrap(); let mut queue: VecDeque<(usize, usize)> = VecDeque::new(); queue.push_front((1, 1)); let mut visited: HashSet<usize> = HashSet::new(); while !queue.is_empty() { let (now, cost) = queue.pop_front().unwrap(); if now == n { println!("{}", cost); return; } let step = format!("{:b}", &now).chars().filter(|c| c == &'1').count(); let prev = now - step; if prev > 0 && !visited.contains(&prev) { visited.insert(prev); queue.push_back((prev, cost + 1)); } let prog = now + step; if prog <= n && !visited.contains(&prog) { visited.insert(prog); queue.push_back((prog, cost + 1)); } } println!("-1"); }