結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2014-11-01 05:53:09 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 806 bytes |
コンパイル時間 | 613 ms |
コンパイル使用メモリ | 64,560 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:05:35 |
合計ジャッジ時間 | 1,524 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <queue> using namespace std; const int INF = 1 << 29; int dp[10010]; int solve(int N){ for(int i=1;i<=N;i++)dp[i] = INF; queue<int> Q; dp[1] = 0; Q.push(1); while(!Q.empty()){ int now = Q.front(); Q.pop(); int cost = dp[now]; int c = __builtin_popcount(now); if(now - c >= 1 && cost + 1 < dp[now - c]){ dp[now - c] = cost + 1; Q.push(now - c); } if(now + c <= N && cost + 1 < dp[now + c]){ dp[now + c] = cost + 1; Q.push(now + c); } } if(dp[N] == INF)return -1; return dp[N] + 1; } int main(){ int N; cin >> N; cout << solve(N) << endl; return 0; }