CF2109C3 Hacking Numbers (Hard Version)
题目描述
这是该问题的困难版本。在此版本中，你能发送的指令限制将在题目描述中说明。只有在解决所有版本的问题后才能进行 hack。
这是一个交互式问题。
欢迎，决斗者们！在这个交互式挑战中，存在一个未知整数 $x$（$1 \le x \le 10^9$）。你需要通过利用"Mathmech"怪兽的力量，将其变为输入中给定的整数 $n$。你可以发送以下指令之一：
| 指令 | 约束条件 | 结果 | 更新操作 | 裁判响应 |
|---------------|-----------------------------------|-----------------------|--------------------------|----------|
| "add $y$" | $-10^{18} \le y \le 10^{18}$ | $\mathrm{res} = x + y$ | 若 $1 \le \mathrm{res} \le 10^{18}$，则 $x \leftarrow \mathrm{res}$ | "1" |
| | | | 否则 $x \leftarrow x$ | "0" |
| "mul $y$" | $1 \le y \le 10^{18}$ | $\mathrm{res} = x \cdot y$ | 若 $1 \le \mathrm{res} \le 10^{18}$，则 $x \leftarrow \mathrm{res}$ | "1" |
| | | | 否则 $x \leftarrow x$ | "0" |
| "div $y$" | $1 \le y \le 10^{18}$ | $\mathrm{res} = x/y$ | 若 $y$ 整除 $x$，则 $x \leftarrow \mathrm{res}$ | "1" |
| | | | 否则 $x \leftarrow x$ | "0" |
| "digit" | — | $\mathrm{res} = S(x)$ $^{\text{∗}}$ | 总是 $x \leftarrow \mathrm{res}$ | "1" |
设 $f(n)$ 为最小整数，使得对于所有 $x$（$1 \le x \le 10^9$），都存在一个由 $f(n)$ 条指令组成的序列能将 $x$ 转换为 $n$。你事先不知道 $x$ 的值。你需要找到这样的 $f(n)$，使得无论 $x$ 是多少，你都能用最多 $f(n)$ 条指令将其转换为 $n$。
你的任务是用最多 $f(n)$ 条指令将 $x$ 变为 $n$。
$^{\text{∗}}$ $S(n)$ 是一个函数，返回非负整数 $n$ 的各位数字之和。例如，$S(123) = 1 + 2 + 3 = 6$。
输入格式
每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 5000$）。接下来是测试用例描述。
每个测试用例的第一行也是唯一一行包含一个整数 $n$（$1 \le n \le 10^9$）。
每个测试用例的交互从读取整数 $n$ 开始。
发送指令时，按以下格式输出一行：
- "add $y$"：将 $x$ 加上整数 $y$（$-10^{18} \le y \le 10^{18}$）。裁判将输出"1"表示 $x + y$ 在 $[1, 10^{18}]$ 内（成功），否则输出"0"。若成功，更新 $x \leftarrow x + y$。
- "mul $y$"：将 $x$ 乘以正整数 $y$（$1 \le y \le 10^{18}$）。裁判将输出"1"表示 $x \cdot y$ 在 $[1, 10^{18}]$ 内（成功），否则输出"0"。若成功，更新 $x \leftarrow x \cdot y$。
- "div $y$"：将 $x$ 除以正整数 $y$（$1 \le y \le 10^{18}$）。裁判将输出"1"表示 $y$ 是 $x$ 的因数（成功），否则输出"0"。若成功，更新 $x \leftarrow \frac{x}{y}$。
- "digit"：将 $x$ 设为其各位数字之和。裁判总是输出"1"并更新 $x \leftarrow S(x)$。
注意指令区分大小写。
当你确定 $x$ 等于 $n$ 时，按以下格式输出一行：
- "!"——裁判将输出"1"表示 $n$ 等于 $x$，否则输出"-1"。
注意回答指令不计入指令限制。
如果你的程序对一个测试用例发送超过 $f(n)$ 条指令（$f(n)$ 如上所述）或发送无效指令，裁判将返回"-1"。收到此响应后，你的程序应立即终止以避免被判错误答案。
在打印指令后，请勿忘记换行并刷新输出缓冲区，否则会因空闲超时被判失败。具体操作如下：
- C++：使用 `fflush(stdout)` 或 `cout.flush()`；
- Java：使用 `System.out.flush()`；
- Python：使用 `sys.stdout.flush()`；
- Rust：使用 `std::io::stdout().flush()`；
- 其他语言请参考文档。
交互器是非自适应的。未知整数 $x$ 在交互过程中不会改变。
### Hack 格式
要进行 hack，请使用以下格式：
第一行包含一个整数 $t$（$1 \leq t \leq 5000$）——测试用例数量。
每个测试用例的第一行包含两个正整数 $n$ 和 $x$（$1 \leq n,x \leq 10^9$）——分别表示目标值和未知整数的初始值。
输出格式
The interaction for each test case begins by reading the integer $ n $ .
To send a command, output a line in the following format:
- "add $ y $ " Add some integer $ y $ ( $ -10^{18} \le y \le 10^{18} $ ) to $ x $ . The jury will output "1" if $ x + y $ is within $ [1, 10^{18}] $ (successful), and "0" otherwise. If successful, update $ x \leftarrow x + y $ .
- "mul $ y $ " Multiply $ x $ by a positive integer $ y $ ( $ 1 \le y \le 10^{18} $ ). The jury will output "1" if $ x \cdot y $ is within $ [1, 10^{18}] $ (successful), and "0" otherwise. If successful, update $ x \leftarrow x \cdot y $ .
- "div $ y $ " Divide $ x $ by a positive integer $ y $ ( $ 1 \le y \le 10^{18} $ ). The jury will output "1" if $ y $ is a divisor of $ x $ (successful), and "0" otherwise. If successful, update $ x \leftarrow \frac{x}{y} $ .
- "digit" Make $ x $ equal to the sum of its digits. The jury will always output "1" and update $ x \leftarrow S(x) $ .
Note that commands are case sensitive.
When you have determined that $ x $ is equal to $ n $ , output a line in the following format:
- "!" — where the jury will output a "1" if $ n $ is equal to $ x $ , and "-1" otherwise.
Note that answering does not count toward your limit of commands.
If your program makes more than $ f(n) $ commands ( $ f(n) $ is described above) for one test case, or makes an invalid command, then the response to the command will be "-1". After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
After printing a command, do not forget to output the end of the 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;
- sys.stdout.flush() in Python;
- std::io::stdout().flush() in Rust;
- see the documentation for other languages.
The interactor is non-adaptive. The unknown integer $ x $ does not change during the interaction.
Hacks
To hack, use the following format.
The first line should contain a single integer $ t $ ( $ 1 \leq t \leq 5000 $ ) — the number of test cases.
The first line of each test case should contain two positive integers $ n $ and $ x $ ( $ 1 \leq n,x \leq 10^9 $ ) — denoting the unknown integer and the target value to which it should be made equal, respectively.
说明/提示
**解释**
$\texttt{2}$：共有 2 个测试用例。
$\texttt{100}$：第一个测试用例中，未知整数 $x = 9$，目标值 $n = 100$。
$\texttt{add -10}$ $\texttt{0}$：指令"add -10"返回"0"，因为 $9 + (-10) \le 0$，$x$ 保持为 9。
$\texttt{add 1}$ $\texttt{1}$：指令"add 1"成功，$x$ 变为 10。
$\texttt{mul 10}$ $\texttt{1}$：指令"mul 10"成功，$x$ 变为 100。
$\texttt{!}$ $\texttt{1}$：确认 $x = n$。
$\texttt{5}$：第二个测试用例中，$x = 1234$，$n = 5$。
$\texttt{digit}$ $\texttt{1}$：$x$ 变为各位数字之和 10。
$\texttt{div 2}$ $\texttt{1}$：指令"div 2"成功，$x$ 变为 5。
$\texttt{!}$ $\texttt{1}$：确认 $x = n$。
注意示例中的空行仅为清晰展示，实际交互中不会出现。
翻译由 DeepSeek V3 完成