結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2015-04-26 19:51:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 593 ms |
コンパイル使用メモリ | 67,024 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:19:57 |
合計ジャッジ時間 | 1,556 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <vector> #include <queue> #include "iostream" #include "algorithm" using namespace std; #define MAX 9999999 int bitcount(int a) { int ret = 0; while (a > 0) { ret++; a &= a - 1; } return ret; } int main() { int n; cin>>n; vector<int> dp(n + 1, MAX); queue<int> q; dp[1] = 1; q.push(1); while (!q.empty()) { int current = q.front(); q.pop(); int diff = bitcount(current); for (int i = -diff; i <= diff ; i += diff*2) { if (current+i < 1 || current+i > n || dp[current+i]!=MAX) continue; dp[current + i] = dp[current] + 1; q.push(current + i); } } if (dp[n] == MAX) cout<<-1<<endl; else cout<<dp[n]<<endl; return 0; }