結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2025-05-05 04:02:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 5,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 12,931 ms |
コンパイル使用メモリ | 406,920 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-05-05 04:02:27 |
合計ジャッジ時間 | 14,533 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
/* * Author: srtry * Created: 2025-05-05T02:26:22+09:00 * Coding: utf-8-unix */ use proconio::input; use std::io::{stdout,Write,BufWriter}; use std::collections::VecDeque; fn main() { input!{ n:usize } let out = stdout(); let mut out = BufWriter::new(out.lock()); let mut dp:Vec<Option<usize>> = vec![None;n+1]; let mut set:VecDeque<usize> = VecDeque::from([1]); dp[1] = Some(1); let mut pos:Option<usize>; loop { pos = set.pop_front(); match pos { Some(x) => { let step:usize = x.count_ones() as usize; if x+step <= n { match dp[x+step] { None => { dp[x+step] = Some(dp[x].unwrap() + 1); set.push_back(x+step); if x+step == n { break; } }, Some(_) => (), } } if x-step > 0 { match dp[x-step] { None => { dp[x-step] = Some(dp[x].unwrap() + 1); set.push_back(x-step); if x-step == n { break; } }, Some(_) => (), } } }, None => break, } } match dp[n] { Some(x) => write!(out, "{}", x).unwrap(), None => write!(out, "-1").unwrap(), } }