<|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++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

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

    long long q;
    int c;

    cin >> q >> c;

    /*
        dp[n] = maximum number of hidden values we can guarantee
                to find 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

        Explanation:
            First guess splits the interval into:
                - lower part
                - the guessed value itself
                - upper part

            The next c guesses are made before the first answer arrives.
            Put those blind guesses on one side.

            One branch can then use n - 1 guesses.
            The other branch loses those c blind guesses and can use
            only n - c - 1 guesses.

            Therefore:
                dp[n] = dp[n - 1] + dp[n - c - 1] + 1
    */

    int size = c + 2;

    /*
        Circular buffer.

        We only need:
            dp[n - 1]
            dp[n - c - 1]

        The largest backward distance is c + 1,
        so size c + 2 is safe.
    */
    vector<long long> dp(size, 0);

    for (long long n = 1; ; n++) {
        long long value = 0;

        if (n > c) {
            /*
                Apply recurrence.

                Because dp is stored circularly, we access indices modulo size.
            */
            value = dp[(n - 1) % size] + dp[(n - c - 1) % size] + 1;
        }

        // Store dp[n] in the circular buffer.
        dp[n % size] = value;

        // First n for which we can cover q numbers is the answer.
        if (value >= q) {
            cout << n << '\n';
            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()
```