## 1. Abridged problem statement

There is a number hidden in the range `1..q`. You may repeatedly guess integers. Normally, after each guess you are told whether the hidden number is smaller, greater, or equal to your guess.

However, this machine answers with delay `c`: after your `i`-th guess, it gives the answer to your `(i-c)`-th guess. For the first `c` guesses, it outputs nothing.

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

Constraints:

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

---

## 2. Detailed editorial

Let:

```text
f(n, c) = maximum size of an interval that can always be solved in at most n guesses
          when answers are delayed by c guesses.
```

We need the smallest `n` such that:

```text
f(n, c) >= q
```

For simplicity, write `f(n)` for fixed `c`.

### Base case

If `n <= c`, then no answer can arrive yet, because every answer is delayed by `c` guesses.

So:

```text
f(n) = 0 for n <= c
```

This also explains sample 2:

```text
q = 1, c = 1
```

Even if we guess `1` immediately, we only receive `"Correct"` after one more guess, so the answer is `2`.

---

### Recurrence

Consider an optimal strategy using `n` guesses.

Let the first guess be a splitter `m`.

Before the answer to the first guess arrives, we must already make `c` more guesses blindly. That means guesses:

```text
q_1, q_2, ..., q_{c+1}
```

are all fixed before we know whether the hidden number is smaller or greater than `q_1`.

The optimal strategy is to put those `c` blind follow-up guesses on one side of the first splitter.

Suppose we put them below the first guess.

Then there are three cases:

---

### Case 1: hidden number equals the first guess

Then we eventually receive `"Correct"`.

This accounts for `1` possible number.

---

### Case 2: hidden number is smaller than the first guess

The guesses `q_2, ..., q_n` form a delayed-search strategy of length `n - 1`.

So the lower side can contain at most:

```text
f(n - 1)
```

numbers.

---

### Case 3: hidden number is greater than the first guess

The `c` blind guesses after the first one were all below the splitter, so they are useless for this branch.

Only guesses:

```text
q_{c+2}, q_{c+3}, ..., q_n
```

remain useful.

There are:

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

such guesses.

So the upper side can contain at most:

```text
f(n - c - 1)
```

numbers.

---

Therefore:

```text
f(n) = f(n - 1) + f(n - c - 1) + 1
```

with:

```text
f(n) = 0 for n <= c
```

For `c = 0`, this becomes:

```text
f(n) = 2 * f(n - 1) + 1
```

so:

```text
f(n) = 2^n - 1
```

which is exactly ordinary binary search.

---

### Why this recurrence is optimal

The first guess splits the interval into lower part, the guessed value itself, and upper part.

Before the first answer arrives, the next `c` guesses are made without knowing which side is correct.

If some of these blind guesses are spent on the lower side, they may help only in the lower branch. If they are spent on the upper side, they may help only in the upper branch.

The best total coverage is achieved by committing all blind guesses to one side. Then one branch gets an almost full strategy of length `n - 1`, and the other branch loses those `c` guesses and gets only `n - c - 1` useful guesses.

Thus the maximum guaranteed searchable interval satisfies:

```text
f(n) = f(n - 1) + f(n - c - 1) + 1
```

---

### Computing the answer

We iterate `n = 1, 2, 3, ...` and compute `f(n)` until:

```text
f(n) >= q
```

Then `n` is the answer.

The recurrence only needs:

```text
f(n - 1)
f(n - c - 1)
```

So we do not need to store all values. A circular buffer of size `c + 2` is enough.

Why `c + 2`?

The largest backward distance needed is from `n` to `n - c - 1`, which is `c + 1`. To avoid overwriting needed values, we use size `c + 2`.

---

### Complexity

Let `answer` be the required number of guesses.

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

This is fast enough for the given constraints.

---

## 3. 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;
}
```

---

## 4. Python solution with detailed comments

```python
import sys
# Import sys for fast input reading.


def solve():
    # Read all input tokens.
    data = sys.stdin.read().split()

    # q is the number of possible hidden values.
    q = int(data[0])

    # c is the response delay.
    c = int(data[1])

    # We define:
    #
    # dp[n] = maximum interval size solvable in n guesses.
    #
    # Base:
    #   dp[n] = 0 for n <= c
    #
    # Recurrence:
    #   dp[n] = dp[n - 1] + dp[n - c - 1] + 1
    #
    # We only need two older values:
    #   dp[n - 1]
    #   dp[n - c - 1]
    #
    # Therefore a circular buffer of size c + 2 is enough.
    size = c + 2

    # Initialize circular buffer with zeros.
    # These zeros also represent all base values dp[n] = 0 for n <= c.
    dp = [0] * size

    # Start checking n = 1, 2, 3, ...
    n = 1

    while True:
        # By default, dp[n] is 0.
        # This is correct when n <= c because no answer has arrived yet.
        value = 0

        if n > c:
            # Apply recurrence:
            #
            # dp[n] = dp[n - 1] + dp[n - c - 1] + 1
            #
            # Use modulo indexing because dp is stored as a circular buffer.
            value = dp[(n - 1) % size] + dp[(n - c - 1) % size] + 1

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

        # Once we can cover at least q numbers, n guesses are sufficient.
        # Because n increases one by one, this n is minimal.
        if value >= q:
            print(n)
            return

        # Try the next number of guesses.
        n += 1


if __name__ == "__main__":
    # Run the solver.
    solve()
```

---

## 5. Compressed editorial

Let `f(n)` be the maximum number of possible hidden values solvable in `n` guesses with delay `c`.

If `n <= c`, no answer can arrive, so:

```text
f(n) = 0
```

For `n > c`, make the first guess as a splitter. The next `c` guesses are made blindly before the first answer arrives.

Put those blind guesses on one side. Then:

- one branch can use `n - 1` remaining guesses;
- the other branch loses the `c` blind guesses and can use only `n - c - 1` guesses;
- the first guessed value itself adds `1`.

Therefore:

```text
f(n) = f(n - 1) + f(n - c - 1) + 1
```

For `c = 0`, this becomes ordinary binary search:

```text
f(n) = 2f(n - 1) + 1
```

Compute `f(n)` increasing `n` until `f(n) >= q`. Since the recurrence only needs `f(n - 1)` and `f(n - c - 1)`, store values in a circular buffer of size `c + 2`.

Complexities:

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