結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2018-06-09 14:38:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 43 ms / 5,000 ms |
コード長 | 1,211 bytes |
コンパイル時間 | 684 ms |
コンパイル使用メモリ | 69,288 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:02:04 |
合計ジャッジ時間 | 2,248 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <utility> #include <vector> #include <queue> using namespace std; int count(int n) { int cnt = 0; while (n > 0) { if (n % 2 == 1) cnt++; n = n / 2; } return cnt; } bool in(vector<int> v, int n) { for (auto var : v) { if (var == n) return true; } return false; } int solve(int n) { queue<pair<int, int>> q; q.push(make_pair(1, 1)); vector<int> v; v.push_back(1); while (!q.empty()) { pair<int, int> tmp = q.front(); int num = tmp.first; int cnt = tmp.second; q.pop(); if (num == n) return cnt; int forward = num + count(num); int backward = num - count(num); if (forward <= n) { if (!in(v, forward)) { q.push(make_pair(forward, cnt+1)); v.push_back(forward); } } if (backward > 0) { if (!in(v, backward)) { q.push(make_pair(backward, cnt+1)); v.push_back(backward); } } } return -1; } int main(int argc, char const* argv[]) { int n; cin >> n; cout << solve(n) << endl; return 0; }