結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2018-10-30 16:01:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 649 bytes |
コンパイル時間 | 1,853 ms |
コンパイル使用メモリ | 199,328 KB |
最終ジャッジ日時 | 2025-01-06 15:08:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; int main() { int n; cin >> n; vi dp(n + 1, 1e9); dp[1] = 0; queue<int> que; que.push(1); while (que.size()) { int t = que.front(); que.pop(); int p = __builtin_popcount(t); int dx[] = {-1, 1}; for (int i = 0; i < 2; i++) { int k = t + dx[i] * p; if (1 <= k && k <= n && dp[t] + 1 < dp[k]) { dp[k] = dp[t] + 1; que.push(k); } } } cout << (dp[n] == 1e9 ? -1 : dp[n] + 1) << endl; }