p287.ans1
======================
10

=================
p287.ans2
======================
2

=================
p287.ans3
======================
16

=================
p287.ans4
======================
17

=================
p287.ans5
======================
11

=================
p287.ans6
======================
41

=================
p287.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t q;
int c;

void read() { cin >> q >> c; }

void solve() {
    // Every answer arrives c queries late, so when we decide q_i we have
    // only seen the responses to q_1, ..., q_{i-c-1}. Out of the n queries
    // we make, only q_1, ..., q_{n-c} can ever yield "Correct!" within n
    // steps; the last c queries are pure padding spent waiting for the
    // answer to q_{n-c} to come back. In particular q_1, ..., q_{c+1} are
    // all committed completely blindly, and q_{c+2} is the first query
    // informed by q_1's outcome.
    //
    // Let f(n, c) be the largest range we can guarantee to crack in n
    // queries with delay c. We pick q_1 = m as the splitter and place the
    // c blind followups q_2, ..., q_{c+1} strictly below m. Once q_1's
    // answer arrives the game branches:
    //
    //   - In the "less" branch (target < m) the suffix q_2, ..., q_n is
    //     itself a delay-c game of length n-1 on the lower segment. The c
    //     values we already committed there are exactly the first c entries
    //     of that sub-game's blind prefix, and q_{c+2} closes the prefix
    //     once the branch is known. So this side covers up to f(n-1, c).
    //
    //   - In the "greater" branch (target > m) the c values placed below m
    //     are useless, as their answers will always be "less than", so only
    //     the fresh queries q_{c+2}, ..., q_n contribute. They form a clean
    //     delay-c game of length n-c-1, covering up to f(n-c-1, c).
    //
    // Any other split of the c blind followups between the two sides only
    // shrinks the achievable range, so the bound is tight:
    //
    //     f(n, c) = f(n-1, c) + f(n-c-1, c) + 1,    f(n, c) = 0 for n <= c.
    //
    // For c = 0 this collapses to f(n, 0) = 2^n - 1, the usual trichotomic
    // search. For c >= 1 the dominant root of x^{c+1} = x^c + 1 sits just
    // above 1, so the answer can grow into the millions for q = 10^15 and
    // c = 10^6. We only ever need the last c+1 entries of f, so a circular
    // buffer of size c+2 is enough. We unroll the recurrence and stop the
    // moment the running value reaches q.
    //
    // This problem is commonly known as delayed binary search, and there
    // are a fair bit of results in academia. One example is:
    //
    //     https://www.researchgate.net/publication/257428752_Delayed_
    //             Binary_Search_or_Playing_Twenty_Questions_with_a_
    //             Procrastinator

    int sz = c + 2;
    vector<int64_t> dp(sz, 0);
    for(int64_t n = 1;; n++) {
        int64_t val = 0;
        if(n > c) {
            val = dp[(n - 1) % sz] + dp[(n - c - 1) % sz] + 1;
        }
        dp[n % sz] = val;
        if(val >= q) {
            cout << n << '\n';
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p287.in1
======================
21 2


=================
p287.in2
======================
1 1

=================
p287.in3
======================
65535 0


=================
p287.in4
======================
65536 0


=================
p287.in5
======================
111 1


=================
p287.in6
======================
21 20


=================
statement.txt
======================
287. Amusing Qc Machine
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Qc was asked to write a program to simulate a game "Guess a number". The program selects some integer number from 1 to q, and asks the player to find it.
The program interacts with the player in the following way. The player inputs some integer number, and the program tells whether the player's number is equal, less than, or greater than the selected number. For example, for q = 8 the dialog could look in the following way:

- Player: 4
- Program: Greater than 4
- Player: 6
- Program: Less than 6
- Player: 3
- Program: Greater than 3
- Player: 5
- Program: Correct! It's 5. You have found it in 4 turns.

Using this simple game, people may, for example, study the method of binary search --- the optimal strategy to win with a minimal number of questions.
The program was expected to work this way, but... Qc would not be himself if he did not bring us his new joke! Qc has intentionally inserted some bugs into his program, so that it worked a bit different compared to the way described above. The Qc Machine (as Qc has proudly called it) selects the number from 1 to q and asks the player to find it, but in the dialog the program does not answer the questions as expected. Instead the Qc machine answers the question that was asked c questions ago. So, after entering the i-th number, the player receives the information whether his (i-c)-th number was correct, less than, or greater than needed.
For example, the algorithm, programmed in the Qc machine could have the following dialog with the player for q=21 and c=2:

- Player: 5
- Qc machine outputs nothing
- Player: 9
- Qc machine outputs nothing
- Player: 3
- Qc machine: Greater than 5
- Player: 7
- Qc machine: Less than 9
- Player: 6
- Qc machine: Greater than 3
- Player: 1
- Qc machine: Correct! It's 7. You have found it in 6 turns.


There were many attempts to find the optimal strategy in game with Qc's rules, but none of them was successful. Only Qc knows the optimal strategy, so your task for this contest is to find it, and for given q and c output the minimal number of steps required in the worst case to find the number selected by the Qc machine.

Input
Input contains two integer numbers: q and c (1 <= q <= 10^15, 0 <= c <= 10^6).

Output
Output a single integer n --- the number of questions required to find the selected integer number from 1 to q on the Qc machine with a delay parameter c in the worst case.

Sample test(s)

Input
Test #1
21 2

Test #2
1 1

Test #3
65535 0

Test #4
65536 0

Test #5
111 1

Test #6
21 20

Output
Test #1
10

Test #2
2

Test #3
16

Test #4
17

Test #5
11

Test #6
41
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

=================
