Vabank

题意翻译

### 题目描述 **本题是一道交互题。** 你需要猜测一个你不知道的整数 $M$。 你有最多 $105$ 次询问机会且初始有一个分值 $P=1$，每次询问你需要给出整数 $X$，接下来： - 如果 $X\leq M$，评测机会输入 `Lucky!` ，同时你的分值 $P$ 增加 $X$。 - 如果 $X>M$，同时 $P\geq X$，评测机会输入 `Fraudster!`，同时你的分值 $P$ 减少 $X$。 - 如果 $X>M$，同时 $P<X$（或是询问次数过多），评测机输入 `Fired!`，此时你应该立即结束程序并得到 `Wrong Answer` 的结果。 在不得到 `Fired!` 的结果下正确地输出 $M$ 的值。$T$ 组数据。 ### 输入格式 第一行一个整数 $T(1\leq T\leq10^3)$ 表示数据组数。 对于每组数据，没有额外的输入数据，但保证 $0\leq M\leq 10^{14}$。 ### 交互格式 如果你希望询问，请先输出一个 `?` 后输出你询问中所对应的整数 $X(1\leq X\leq10^{14})$，接下来你会得到评测机输入的一个字符串，具体意义见上。 如果你希望回答，请先输出一个 `!` 之后输出你认为的 $M$ 的值，之后立即开始下一组数据。 注意刷新缓冲区，否则可能会得到 `Idleness limit exceeded` 的结果。

题目描述

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.

输入输出格式

输入格式

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} $ .

输出格式

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 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} $ ).

输入输出样例

输入样例 #1

1

Lucky!

Lucky!

Lucky!

Lucky!

Lucky!

Fraudster!

输出样例 #1

? 1

? 2

? 3

? 4

? 5

? 6

! 5

说明

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.