結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-03-06 23:07:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,080 bytes |
コンパイル時間 | 670 ms |
コンパイル使用メモリ | 75,528 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:56:43 |
合計ジャッジ時間 | 1,676 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <queue> #include <map> using namespace std; int bit(int x){ int response=(x%2); while(x/=2) response+=(x%2); return response; } struct Struct{ int n,count; Struct(int n=0,int count=0):n(n),count(count){}; }; int main(){ int N; cin >> N; queue<Struct> circle; circle.push(Struct(1,1)); map<int,bool> dp; bool sign=false; Struct now; while(circle.size()!=0){ now=circle.front();circle.pop(); if(now.n==N){ sign=true; break; } if(dp[now.n]!=0)continue; if(now.n<0 || now.n>N)continue; dp[now.n]=true; int step=bit(now.n); circle.push(Struct(now.n-step,now.count+1)); circle.push(Struct(now.n+step,now.count+1)); } if(sign) cout<<now.count<<endl; else cout<<-1<<endl; return 0; }