結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2019-06-29 01:38:51 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,010 bytes |
コンパイル時間 | 526 ms |
コンパイル使用メモリ | 64,816 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:23:24 |
合計ジャッジ時間 | 1,468 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <queue> using namespace std; int bitCount(int num) { int cnt = 0; if (num == 0) { return 0; } while (1) { num &= num - 1; cnt++; if (num == 0) { break; } } return cnt; } int main() { int N; int dist[10010]; cin >> N; for (int i = 0; i <= N; i++) { dist[i] = -1; } dist[1] = 1; queue<int> q; q.push(1); while (!q.empty()) { int now = q.front(); q.pop(); int bit = bitCount(now); if (1 <= (now - bit)) { if (dist[now - bit] < 0) { dist[now - bit] = dist[now] + 1; q.push(now - bit); } } if (now + bit <= N) { if (dist[now + bit] < 0) { dist[now + bit] = dist[now] + 1; q.push(now + bit); } } } cout << dist[N] << endl; }