結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2019-04-17 16:30:16 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,959 bytes |
コンパイル時間 | 788 ms |
コンパイル使用メモリ | 93,412 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:18:17 |
合計ジャッジ時間 | 1,839 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<iostream> #include<cmath> #include<vector> #include<set> #include<algorithm> #include<tuple> #include<utility> #include<cctype> #include<climits> #include<map> #include<queue> #include<functional> #include<stack> #include<iomanip> #include<sstream> #include<bitset> using namespace std; #define REP(i,a,n) for(int i=a;i<n;++i) #define REPL(i,a,n) for(ll i=a;i<n;++i) #define RUP(a,b) ((a+b-1)/(b)) #define ENT "\n" #define SORTVG(v) sort(v.begin(),v.end(),greater<>()) #define SORTV(v) sort(v.begin(),v.end()) #define ALL(v) (v).begin(),(v).end() #define MOD 1000000007 #define INF LLONG_MAX/2 typedef long long ll; typedef tuple<int,int,bool> Tb; typedef pair<int,int> Pii; typedef vector<int> Vi; template<class T> void chmax(T& a, T b) {if(a < b){a=b;}} template<class T> void chmin(T& a, T b) {if(a > b){a=b;}} template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}} template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}} int bits(int num) { int dig; int sum = 0; while(num){ dig = num % 2; sum = sum + dig; num = num / 2; } return sum; } int atcoder(){ int n; cin>>n; Vi visited = Vi(n+1,0); visited[1] = 1; queue< pair<int,int> > q; q.push(make_pair(1,1)); while(q.size()>0){ int now= q.front().first; int depth= q.front().second; q.pop(); int bitcount=bits(now); if(now+bitcount<=n && visited[now+bitcount]==0){ visited[now+bitcount]=depth+1; q.push(make_pair(now+bitcount,depth+1)); } if(1<=now-bitcount && visited[now-bitcount]==0){ visited[now-bitcount]=depth+1; q.push(make_pair(now-bitcount,depth+1)); } } cout<<(visited[n]!=0 ? visited[n] : -1)<<ENT; return 0; } signed main() { cin.tie(0); ios::sync_with_stdio(false); atcoder(); return 0; }