結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2017-10-21 22:37:19 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,150 bytes |
コンパイル時間 | 791 ms |
コンパイル使用メモリ | 85,400 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-01 08:49:51 |
合計ジャッジ時間 | 1,870 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
/* * main.cpp * * Created on: 2017/10/06 * Author: sep */ #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cmath> #include <cstring> #include <vector> #include <algorithm> #include <map> #include <queue> using namespace std; inline int main003(); inline int main2(); inline int main3(); inline int main4(); int main() { main003(); return 0; } inline int get_bit(int x) { int c = 0; while (x) { if (x & 1) c++; x >>= 1; } return c; } inline int main003() { int num; int route, v1, v2, bit_count; int result = 0; map<int, int> v; queue<int> q; cin >> num; q.push(1); v[1] = 1; while (!q.empty()) { route = q.front(); q.pop(); if (route == num) { result = v[route]; break; } bit_count = get_bit(route); v1 = route + bit_count; v2 = route - bit_count; if ((v1 <= num) && (v[v1] == 0 || v[route] + 1 < v[v1])) { v[v1] = v[route] + 1; q.push(v1); } if ((0 < v2) && (v[v2] == 0 || v[route] + 1 < v[v2])) { v[v2] = v[route] + 1; q.push(v2); } } if (result == 0) { cout << -1; } else { cout << result; } return 0; }