結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2016-08-23 18:12:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 113 ms / 5,000 ms |
コード長 | 1,355 bytes |
コンパイル時間 | 12,988 ms |
コンパイル使用メモリ | 402,600 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:03:00 |
合計ジャッジ時間 | 15,648 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:18:9 | 18 | let mut num: usize = num.trim().parse().ok().expect("ERROR"); | ----^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default
ソースコード
use std::cmp; fn num2bin(p: &usize) -> usize { let mut x: usize = *p; let mut cnt: usize = 0; while x > 0 { cnt += x & 1; x = x >> 1; } cnt } fn main() { let mut num = String::new(); std::io::stdin().read_line(&mut num).ok().expect("ERROR"); let mut num: usize = num.trim().parse().ok().expect("ERROR"); let mut dp = vec![-1; num+1]; let mut dp_new = vec![-1; num+1]; dp[1] = 1; dp_new[1] = 1; let mut flag = true; while flag { flag = false; for i in 1..num+1 { if dp[i] < 1 { continue; } let inc = num2bin(&i); if i-inc > 1 { if dp[i-inc] < 0 { dp_new[i-inc] = dp[i] + 1; } else { dp_new[i-inc] = cmp::min(dp[i-inc], dp[i]+1); } } if i+inc <= num { if dp[i+inc] < 0 { dp_new[i+inc] = dp[i] + 1; } else { dp_new[i+inc] = cmp::min(dp[i+inc], dp[i]+1); } } } for i in 1..num+1 { if dp[i] != dp_new[i] { flag = true; } dp[i] = dp_new[i]; } } println!("{}", dp[num]); }