結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2016-04-06 00:59:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,302 bytes |
コンパイル時間 | 577 ms |
コンパイル使用メモリ | 71,436 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:48:57 |
合計ジャッジ時間 | 1,613 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <set> #include <map> #include <queue> #include <climits> #include <cassert> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define INF INT_MAX/3 #define LINF LLONG_MAX/3 #define MP make_pair #define PB push_back #define ALL(v) (v).begin(),(v).end() typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; int N; int one[10001]; int used[10001]; int cntone(int n){ int cnt=0; while(n>0){ if(n%2) cnt++; n/=2; } return cnt; } int main(){ cin >> N; REP(i,10001) one[i] = cntone(i); REP(i,10001) used[i] = INF; used[1] = 1; queue<int> que; que.push(1); while(!que.empty()){ int p = que.front(); que.pop(); if(p+one[p]>=1 and p+one[p]<=N){ if(used[p+one[p]] > used[p]+1){ used[p+one[p]] = used[p]+1; que.push(p+one[p]); } } if(p-one[p]>=1 and p-one[p]<=N){ if(used[p-one[p]] > used[p]+1){ used[p-one[p]] = used[p]+1; que.push(p-one[p]); } } } if(used[N]==INF) cout << -1 << endl; else cout << used[N] << endl; return 0; }