結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-03-27 01:42:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,011 bytes |
コンパイル時間 | 715 ms |
コンパイル使用メモリ | 86,260 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:57:43 |
合計ジャッジ時間 | 1,725 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<iostream> #include<string> #include<algorithm> #include<cmath> #include<iomanip> #include<cstring> #include<map> #include<vector> #include<queue> #include<climits> #include<set> #include<utility> using namespace std; typedef long long int ll; bool flag[10010]; int num[10010]; static const int INF=1e8; int cnt(int now){ int ans=0; while(now>0){ if(now%2==1){ ans++; } now/=2; } return ans; } int main(){ memset(flag, 0, sizeof(flag)); for(int i=0; i<10010; i++){ num[i]=INF; } num[1]=1; int n; cin >> n; queue<int> q; q.push(1); while(!q.empty()){ int now=q.front(); q.pop(); if(flag[now]){ continue; } flag[now]=true; int d=cnt(now); if(1<=now-d && now-d<=n && flag[now-d]==false){ num[now-d]=min(num[now]+1, num[now-d]); q.push(now-d); } if(1<=now+d && now+d<=n && flag[now+d]==false){ num[now+d]=min(num[now]+1, num[now+d]); q.push(now+d); } } if(flag[n]){ cout << num[n] << endl; } else { cout << -1 << endl; } return 0; }