<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
## 1. Abridged problem statement

There is a hidden integer from `1` to `q`.

You repeatedly guess integers. Normally, after each guess, the program tells you whether the hidden number is smaller, greater, or equal to your guess.

However, the Qc Machine delays every answer by `c` guesses:

- after guess `1`, no answer is received until guess `c + 1`;
- after guess `i`, you receive the answer to guess `i - c`.

Given `q` and `c`, find the minimum number of guesses needed in the worst case to guarantee finding the hidden number.

Constraints:

```text
1 <= q <= 10^15
0 <= c <= 10^6
```

---

## 2. Key observations needed to solve the problem

Let:

```text
dp[n] = maximum number of possible hidden values that can be guaranteed
        to be found in at most n guesses with delay c
```

We need the smallest `n` such that:

```text
dp[n] >= q
```

### Observation 1: No answer arrives during the first `c` guesses

If `n <= c`, then even if we guess the correct number, we will not receive the `"Correct"` response within `n` guesses.

Therefore:

```text
dp[n] = 0 for n <= c
```

For example, if `q = 1` and `c = 1`, we still need `2` guesses:

1. Guess `1`, receive nothing.
2. Make one more guess, receive `"Correct"` for the first guess.

So the answer is `2`.

---

### Observation 2: The first guess splits the interval

Suppose we want to solve an interval using `n` guesses.

Let the first guess be some value `x`.

There are three possibilities:

1. Hidden number is equal to `x`.
2. Hidden number is smaller than `x`.
3. Hidden number is greater than `x`.

The value `x` itself contributes `1` possible hidden number.

---

### Observation 3: The next `c` guesses after the first one are blind

After the first guess, we do not immediately know whether the hidden number is smaller, greater, or equal.

The next `c` guesses must be chosen before we know the answer to the first guess.

So guesses:

```text
1, 2, ..., c + 1
```

are all made without knowing the answer to guess `1`.

The optimal idea is to spend these `c` blind follow-up guesses on one side of the first splitter.

For example, put them all on the lower side.

Then:

- If the hidden number is smaller than the first guess, those guesses are useful.
- If the hidden number is greater than the first guess, those guesses are wasted.

---

### Observation 4: Recurrence

If the hidden number is on the side where the blind guesses were useful, then after the first guess we effectively have:

```text
n - 1
```

guesses left.

So that side can contain up to:

```text
dp[n - 1]
```

numbers.

On the other side, the `c` blind guesses are wasted. The useful guesses start only after those `c` guesses, so we have:

```text
n - c - 1
```

guesses left.

So the other side can contain up to:

```text
dp[n - c - 1]
```

numbers.

Including the first guessed value itself:

```text
dp[n] = dp[n - 1] + dp[n - c - 1] + 1
```

with base:

```text
dp[n] = 0 for n <= c
```

---

### Observation 5: Ordinary binary search is a special case

If `c = 0`, there is no delay.

The recurrence becomes:

```text
dp[n] = dp[n - 1] + dp[n - 1] + 1
dp[n] = 2 * dp[n - 1] + 1
```

So:

```text
dp[n] = 2^n - 1
```

This is exactly ordinary binary search.

---

## 3. Full solution approach based on the observations

We compute `dp[n]` for increasing `n` until `dp[n] >= q`.

The recurrence is:

```text
dp[n] = 0,                              if n <= c
dp[n] = dp[n - 1] + dp[n - c - 1] + 1,  if n > c
```

The answer is the first `n` such that:

```text
dp[n] >= q
```

### Memory optimization

To compute `dp[n]`, we only need:

```text
dp[n - 1]
dp[n - c - 1]
```

So we do not need to store all previous values.

The maximum distance backwards is `c + 1`, so a circular buffer of size:

```text
c + 2
```

is enough.

We use:

```text
dp[index % (c + 2)]
```

to store and retrieve values.

### Overflow note

`q <= 10^15`, so 64-bit integers are enough.

We can stop as soon as `dp[n] >= q`.

### Complexity

Let `answer` be the minimal required number of guesses.

```text
Time complexity:  O(answer)
Memory complexity: O(c)
```

This is sufficient for the given constraints.

---

## 4. C++ Solution

```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;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = sys.stdin.read().split()

    q = int(data[0])
    c = int(data[1])

    """
    dp[n] = maximum number of hidden values that can be guaranteed
            to be found in at most n guesses with delay c.

    Base:
        dp[n] = 0 for n <= c

    Recurrence:
        dp[n] = dp[n - 1] + dp[n - c - 1] + 1

    We need the smallest n such that dp[n] >= q.
    """

    size = c + 2

    """
    Circular buffer.

    To compute dp[n], we only need:
        dp[n - 1]
        dp[n - c - 1]

    Therefore, a buffer of size c + 2 is enough.
    """
    dp = [0] * size

    n = 1

    while True:
        value = 0

        if n > c:
            # Apply recurrence using circular indexing.
            value = dp[(n - 1) % size] + dp[(n - c - 1) % size] + 1

        # Store dp[n].
        dp[n % size] = value

        # Since n increases one by one, the first such n is minimal.
        if value >= q:
            print(n)
            return

        n += 1


if __name__ == "__main__":
    solve()
```