#include using namespace std; #include #include #include using namespace atcoder; using ll = long long; using ld = long double; using P = pair; using Graph = vector>; using vi = vector; using vl = vector; using vll = vector; using vb = vector; using vvi = vector; using vvl = vector; using vvb = vector; using vvll = vector; using vvvll = vector; using vc = vector; using vvc = vector; using vs = vector; using pii = pair; using mint = modint1000000007; const long double EPS = 1e-10; const long long INF = 1e18; const long double PI = acos(-1.0L); #define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++) #define rep(i, n) for (ll i = (0); i < (ll)(n); i++) #define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++) #define repd(i, n) for (ll i = n - 1; i >= 0; i--) #define rrepd(i, n) for (ll i = n; i >= 1; i--) #define ALL(n) begin(n), end(n) #define fore(i, a) for (auto &i : a) #define IN(a, x, b) (a <= x && x < b) #define IN(a, x, b) (a <= x && x < b) #define INIT \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); template inline T CHMAX(T &a, const T b) { return a = (a < b) ? b : a; } template inline T CHMIN(T &a, const T b) { return a = (a > b) ? b : a; } #include // min, max, swap, sort, reverse, lower_bound, upper_bound #include // bitset #include // isupper, islower, isdigit, toupper, tolower #include // int64_t, int*_t #include // printf #include // deque #include // cout, endl, cin #include // map #include // queue, priority_queue #include // set #include // stack #include // string, to_string, stoi #include // tuple, make_tuple #include // unordered_map #include // unordered_set #include // pair, make_pair #include // vector using namespace std; ll GCD(ll m, ll n) { // ベースケース if (n == 0) return m; // 再帰呼び出し return GCD(n, m % n); } ll minlong = 0; long long Power(long long a, long long b, long long m) { long long p = a, Answer = 1; for (int i = 0; i < 63; i++) { ll wari = (1LL << i); if ((b / wari) % 2 == 1) { Answer = (Answer * p) % m; // 「a の 2^i 乗」が掛けられるとき } p = (p * p) % m; } return Answer; } // a ÷ b を m で割った余りを返す関数 long long Division(long long a, long long b, long long m) { return (a * Power(b, m - 2, m)) % m; } // nCr mod 1000000007 を返す関数 long long nCk(ll n, ll r) { const long long M = 1000000007; // 手順 1: 分子 a を求める long long a = 1; for (int i = 1; i <= n; i++) a = (a * i) % M; // 手順 2: 分母 b を求める long long b = 1; for (int i = 1; i <= r; i++) b = (b * i) % M; for (int i = 1; i <= n - r; i++) b = (b * i) % M; // 手順 3: 答えを求める return Division(a, b, M); } using Interval = pair; // nCk mint を返す関数。 ll modnCk(ll n, ll r) { ll a = 1; for (ll i = n; i > n - r; i--) { a *= i; a /= n + 1 - i; } return a; } // 終点時間でsortをかけるのに必要(区間スケジューリング問題など) bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; } vll dycstra(vector>> G, ll N, ll K) { vb kaku(N, false); vll cur(N, INF); cur[K] = 0; priority_queue, vector>, greater>> Q; Q.push(make_pair(cur[K], K)); while (!Q.empty()) { ll pos = Q.top().second; Q.pop(); if (kaku[pos]) continue; kaku[pos] = true; for (ll i = 0; i < G[pos].size(); i++) { ll nex = G[pos][i].first; ll cost = G[pos][i].second; if (cur[nex] > cur[pos] + cost) { cur[nex] = cur[pos] + cost; Q.push(make_pair(cur[nex], nex)); } } } return cur; } template struct BIT { int n; // 要素数 vector bit[300000]; // データの格納先 BIT(int n_) { init(n_); } void init(int n_) { n = n_ + 1; for (int p = 0; p < 2; p++) bit[p].assign(n, 0); } void add_sub(int p, int i, T x) { for (int idx = i; idx < n; idx += (idx & -idx)) { bit[p][idx] += x; } } void add(int l, int r, T x) { // [l,r) に加算 add_sub(0, l, -x * (l - 1)); add_sub(0, r, x * (r - 1)); add_sub(1, l, x); add_sub(1, r, -x); } T sum_sub(int p, int i) { T s(0); for (int idx = i; idx > 0; idx -= (idx & -idx)) { s += bit[p][idx]; } return s; } T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; } // sum'(i)=sum(i)-x(l-i)+xi(sum'(i)は加算後の合計値sum(i)測酸前の合計値) T query(int l, int r) { return sum(r - 1) - sum(l - 1); } // 任意の区間を計算することが可能これは[l,r)の区間和を計算している。 int lower_bound(T w) { // a_1 + a_2 + ... + a_x >= w となるような最小の x // を求める(ただし a_i >= 0) if (w <= 0) { return 0; } else { int x = 0, r = 1; while (r < n) r = r << 1; for (int len = r; len > 0; len = len >> 1) { // 長さlenは1段下るごとに半分に if (x + len < n && bit[x + len] < w) { // 採用するとき w -= bit[x + len]; x += len; } } return x + 1; } } }; vll BFS(vvll &G, ll &x) { vll cut(G.size(), INF); queue Q; Q.push(x); cut[x] = 0; while (!Q.empty()) { ll a = Q.front(); Q.pop(); rep(i, G[a].size()) { if (cut[G[a][i]] > cut[a] + 1) { cut[G[a][i]] = cut[a] + 1; Q.push(G[a][i]); } } } return cut; } template struct UnionFind { vector par; vector rank; vector diff_weight; vector siz; UnionFind(int n = 1, Abel SUM_UNITY = 0) { init(n, SUM_UNITY); } void init(int n = 1, Abel SUM_UNITY = 0) { par.resize(n); rank.resize(n); diff_weight.resize(n); siz.resize(n); for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY, siz[i] = 1; } int root(int x) { if (par[x] == x) { return x; } else { int r = root(par[x]); diff_weight[x] += diff_weight[par[x]]; // 累積和をとることで重みがつけられる。 return par[x] = r; } } Abel weight(int x) { root(x); // 経路圧縮 return diff_weight[x]; // 重みを返す } bool issame(int x, int y) { return root(x) == root(y); // 通常時も同じ } // weight(y) - weight(x) = w となるように merge する bool merge(int x, int y, Abel w) { // x と y それぞれについて、 root との重み差分を補正 w += weight(x); w -= weight(y); // x と y の root へ (x と y が既につながっていたら false を返すようにした) x = root(x); y = root(y); if (x == y) return false; // rank[x] >= rank[y] となるように x と y を swap (それに合わせて w // も符号反転します)これはUnion by // rankと呼ばれ根の高さをO(logN)で抑えられる手法である。 if (rank[x] < rank[y]) swap(x, y), w = -w; // y (のroot) を x (のroot) // の下にくっつける(高さが低い方の根付き木を高いほうに併合する) if (rank[x] == rank[y]) ++rank[x]; siz[x] += siz[y]; par[y] = x; // x が y の親になるので、x と y の差分を diff_weight[y] に記録 diff_weight[y] = w; return true; } Abel diff(int x, int y) { return weight(y) - weight(x); } int size(int x) { return siz[root(x)]; } }; class SegmentTree { public: int dat[600000], siz = 1; // 要素 dat の初期化を行う(最初は全部ゼロ) void init(int N) { siz = 1; while (siz < N) siz *= 2; for (int i = 1; i < siz * 2; i++) dat[i] = 0; } // クエリ 1 に対する処理 void update(int pos, int x) { pos = pos + siz - 1; dat[pos] = x; while (pos >= 2) { pos /= 2; dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]); } } // クエリ 2 に対する処理 // u は現在のセル番号、[a, b) はセルに対応する半開区間、[l, r) // は求めたい半開区間 int query(int l, int r, int a, int b, int u) { if (r <= a || b <= l) return -1000000000; // 一切含まれない場合 if (l <= a && b <= r) return dat[u]; // 完全に含まれる場合 int m = (a + b) / 2; int AnswerL = query(l, r, a, m, u * 2); int AnswerR = query(l, r, m, b, u * 2 + 1); return max(AnswerL, AnswerR); } }; void Yes(bool b) { if (b) cout << "Yes" << endl; else cout << "No" << endl; } vector yaku(long long n) { vector ret; for (long long i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(ret.begin(), ret.end()); // 昇順に並べる return ret; } int main() { ll N, M, K, a, b, c; string S, T; cin >> N; vector>> G(N); reps(i, 1, N) { bitset<32> p(i); a = i - p.count() - 1; b = i + p.count() - 1; if (a >= 0) G[i - 1].push_back(make_pair(a, 1)); if (b <= N - 1) G[i-1].push_back(make_pair(b, 1)); } vll A = dycstra(G,N, 0); if (A[N - 1] == INF) { cout << -1 << endl; return 0; } cout << A[N - 1] +1<< endl; }