Vabank
Contest: Технокубок 2021 - Финал
Difficulty rating: 3200
Tags: binary search, interactive

Gustaw is the chief bank manager in a huge bank. He has unlimited access to the database system of the bank, in a few clicks he can move any amount of money from the bank's reserves to his own private account. However, the bank uses some fancy AI fraud detection system that makes stealing more difficult.

Gustaw knows that the anti-fraud system just detects any operation that exceeds some fixed limit $$$M$$$ euros and these operations are checked manually by a number of clerks. Thus, any fraud operation exceeding this limit is detected, while any smaller operation gets unnoticed.

Gustaw doesn't know the limit $$$M$$$ and wants to find it out. In one operation, he can choose some integer $$$X$$$ and try to move $$$X$$$ euros from the bank's reserves to his own account. Then, the following happens.

- If $$$X \le M$$$, the operation is unnoticed and Gustaw's account balance raises by $$$X$$$ euros.
- Otherwise, if $$$X > M$$$, the fraud is detected and cancelled. Moreover, Gustaw has to pay $$$X$$$ euros from his own account as a fine. If he has less than $$$X$$$ euros on the account, he is fired and taken to the police.

Initially Gustaw has $$$1$$$ euro on his account. Help him find the exact value of $$$M$$$ in no more than $$$105$$$ operations without getting him fired.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$).

For each test case, there is no input prior to your first query, but you can be sure that $$$M$$$ is integer, and $$$0 \le M \le 10^{14}$$$.

Output format:
For each test case, when you know the exact value of $$$M$$$, print a single line with format "! $$$M$$$". After that your program should proceed to the next test case or terminate, if it is the last one.

Interaction format:
When you want to make an operation, print a single line with format "? $$$X$$$", denoting that you try to move $$$X$$$ euros ($$$1 \le X \le 10^{14}$$$). As a response, read a single line that can take the following values:

- "Lucky!", if $$$X \le M$$$. Your balance raises by $$$X$$$.
- "Fraudster!", if $$$X > M$$$. Your balance decreases by $$$X$$$.
- "Fired!", if $$$X > M$$$, but you can't pay $$$X$$$ euros of fine. In this case your program must terminate immediately. You also get this response if you exceed the number of queries.

You can make at most $$$105$$$ such queries in each test case.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks

To make a hack, prepare an input in the following format.

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case is described with a line containing a single integer $$$M$$$ ($$$0 \le M \le 10^{14}$$$).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the example $$$M = 5$$$, so the operation with $$$X = 6$$$ is detected. At this moment, Gustaw's balance is $$$16$$$ euros, so he just pays fine.

Example input:
1

Lucky!

Lucky!

Lucky!

Lucky!

Lucky!

Fraudster!

Example output:
? 1

? 2

? 3

? 4

? 5

? 6

! 5

Editorial:
Our solution consists of two parts. First of all find an upper bound for $$$M$$$. To achieve this, we try to query $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$ and so on until we fail. After the first unsuccessful query we will have $$$0$$$ euro and know that the answer is on some segment $$$[2^k, 2^{k+1})$$$. It takes at most 47 queries.
Now one could do something like the following binary search: take the left border of our segment of money, then on each query try the left border and then the middle. If the queries are successful then all good, otherwise we lose $$$L + \frac{R - L}{2}$$$, where $$$L$$$ is taken at the beginning of this iteration, and all $$$\frac{R - L}{2}$$$ cannot sum up into something greater than the initial left border we obtained, because initially $$$R - L = L$$$, and each time $$$R - L$$$ decreases twice. However, this solution requires another $$$2\log(10^{14})$$$ queries, which is too much.
Let's divide the segment into two non-equal parts sometimes. Note that if the left side of the partition doesn't exceed half of the segment then that extra $$$L$$$ we have is enough to cover all our expenses. Also let's use that we actually get extra $$$M \approx \frac{L + R}{2}$$$ after successful middle queries.
We want our algorithm to look something like the following. Let the current segment equal $$$[l, r]$$$. and the current balance is at least $$$l\cdot y + (r - l)$$$ for some integer $$$y$$$. Then if $$$y = 0$$$ then we query $$$l$$$, and if $$$y > 1$$$ then we query whatever we want on the segment. It is easy to see that after an unsuccessful query our balance is at least $$$l \cdot (y - 1) + (r - l)$$$ (for new $$$l$$$ and $$$r$$$), and after a successful query, we will think that our balance is at least $$$l \cdot (y + 1) + (r - l)$$$ (for new $$$l$$$ or $$$r$$$). The latter is not always the case, we will discuss that later.
Now our balance is described by the only integer $$$y$$$. Let $$$dp[x][y]$$$ equal the maximal $$$d$$$ so that it's possible to find the answer on $$$[l, l + d]$$$ having $$$y\cdot l + d$$$ money initially. Then $$$dp[x][y] = dp[x - 1][y - 1] + dp[x - 1][y + 1]$$$, it is easy to compute and follow in the solution. One can show that $$$dp[k][0] = \binom{k}{[k/2]}$$$. It implies that $$$k\leq 49$$$. This adds up to 97 queries.
Now remember that, if we proceed from $$$(l, r, y)$$$ to $$$(m, r, y + 1)$$$, then our balance was $$$y\cdot l + (r - l)$$$ and became $$$y\cdot l + m$$$, while we need $$$(y + 1)\cdot m$$$ for our estimations. Hence we need some extra cash to cover such "expenses". It can be proven that they don't exceed three of initial $$$L$$$-s, which gives the total of 100 queries.