結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2016-02-24 04:55:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 689 bytes |
コンパイル時間 | 799 ms |
コンパイル使用メモリ | 65,180 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:44:36 |
合計ジャッジ時間 | 1,550 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<iostream> #include<queue> using namespace std; #define NMAX 10000 int bitcount1(int n){ int c=0; while(n!=0){ /*cout<<n<<"-"<<c<<endl;*/ if(n%2==1) c++; n=n>>1; } return c; } int main(){ int N; int dp[NMAX+1]; queue<int> n; cin>>N; for(int i=1;i<=N;i++){ dp[i]=NMAX+1; } n.push(1); dp[1]=1; while(!n.empty()){ int mas=n.front(); n.pop(); int dot=bitcount1(mas); /*cout<<mas<<","<<dot<<endl;*/ if(mas-dot>=1&&dp[mas]+1<dp[mas-dot]){ dp[mas-dot]=dp[mas]+1; n.push(mas-dot); } if(mas+dot<=N&&dp[mas]+1<dp[mas+dot]){ dp[mas+dot]=dp[mas]+1; n.push(mas+dot); } } if(dp[N]==NMAX+1) cout<<"-1"<<endl; else cout<<dp[N]<<endl; }