結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2015-05-20 23:47:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 792 bytes |
コンパイル時間 | 655 ms |
コンパイル使用メモリ | 66,620 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:21:31 |
合計ジャッジ時間 | 1,580 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <algorithm> #include <iostream> #include <queue> using namespace std; #define INF 1<<25 int count1(int a){ int cnt=0; while(a){ if(a&1) cnt++; a>>=1; } return cnt; } int main(){ int n; cin>>n; int search[n+1]; int num[n]; for(int i=0;i<n;i++){ search[i]=INF; num[i]=count1(i+1); } search[0]=1; queue<int> sta; sta.push(0); while(search[n-1]==INF&&sta.size()!=0){ int cur=sta.front(); sta.pop(); if(cur+num[cur]<n){ if(search[cur+num[cur]]>search[cur]+1){ search[cur+num[cur]]=search[cur]+1; sta.push(cur+num[cur]); } } if(cur-num[cur]>0){ if(search[cur-num[cur]]>search[cur]+1){ search[cur-num[cur]]=search[cur]+1; sta.push(cur-num[cur]); } } } if(search[n-1]==INF) search[n-1]=-1; cout<<search[n-1]<<endl; return 0; }