結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2015-06-14 19:38:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,480 bytes |
コンパイル時間 | 759 ms |
コンパイル使用メモリ | 92,696 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:24:34 |
合計ジャッジ時間 | 1,727 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <algorithm> // require sort next_permutation count __gcd reverse etc. #include <cstdlib> // require abs exit atof atoi #include <cstdio> // require scanf printf #include <functional> #include <numeric> // require accumulate #include <cmath> // require fabs #include <climits> #include <limits> #include <cfloat> #include <iomanip> // require setw #include <sstream> // require stringstream #include <cstring> // require memset #include <cctype> // require tolower, toupper #include <fstream> // require freopen #include <ctime> // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() /* No.3 ビットすごろく 幅優先探索 */ using namespace std; typedef long long ll; typedef pair<int, int> P; const int MAX_N = (int)1e4 + 4; const int dr[2] = { -1, 1 }; int d[MAX_N]; void bfs (int N ){ queue<int> que; que.push (1 ); d[1] = 1; while (!que.empty() ){ int curr = que.front(); que.pop(); rep (k, 2 ){ int next = curr + dr[k]*(int)__builtin_popcount (curr ); if (next < 0 || next > N ) continue; if (d[next] == -1 ){ que.push (next ); d[next] = d[curr] + 1; } // end if } // end rep } // end while } int main() { memset (d, -1, sizeof (d ) ); ios_base::sync_with_stdio(0); int N; cin >> N; bfs (N ); cout << d[N] << endl; return 0; }