結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-01-26 22:42:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 849 bytes |
コンパイル時間 | 1,313 ms |
コンパイル使用メモリ | 162,984 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:16:32 |
合計ジャッジ時間 | 2,204 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define MOD 1000000007 #define INF 1000000000 #define PI 3.14159265359 #define EPS 1e-12 int main() { int n; cin >> n; int a[11234]; REP(i, n+1) a[i] = -1; a[1] = 1; queue<int> que; que.push(1); while(!que.empty()) { int i = que.front(); que.pop(); int cnt = __builtin_popcount(i); if(i-cnt >= 1 && a[i-cnt] == -1) { a[i-cnt] = a[i] + 1; que.push(i-cnt); } if(i+cnt <= n && a[i+cnt] == -1) { a[i+cnt] = a[i] + 1; que.push(i+cnt); } } cout << a[n] << endl; }