結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-12-24 00:40:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 1,363 ms |
コンパイル使用メモリ | 162,804 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 09:11:49 |
合計ジャッジ時間 | 2,435 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; using P = pair<int, int>; constexpr ld EPS = 1e-12; constexpr int INF = numeric_limits<int>::max() / 2; constexpr int MOD = 1e9 + 7; int count(int data) { int res = 0; for (; data; data &= data - 1) { res++; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<int> dp(n + 1, INF); queue<int> q; dp[1] = 1; q.push(1); while (!q.empty()) { int v = q.front(); q.pop(); int cnt = count(v); if (v - cnt >= 1) { if (dp[v - cnt] == INF) { dp[v - cnt] = dp[v] + 1; q.push(v - cnt); } } if (v + cnt <= n) { if (dp[v + cnt] == INF) { dp[v + cnt] = dp[v] + 1; q.push(v + cnt); } } } if (dp[n] == INF) cout << -1 << endl; else cout << dp[n] << endl; }