A16467. Hacking Numbers (Medium Version)
编程题
普及+/提高
知识点
题目描述
这是该问题的中等版本。在此版本中，你最多可以发送 $\mathbf{4}$ 条指令。只有在解决所有版本的问题后才能进行 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" |
你需要用最多 $\mathbf{4}$ 条指令使 $x$ 等于 $n$。
$^{\text{∗}}$ $S(n)$ 是一个函数，返回非负整数 $n$ 的各位数字之和。例如，$S(123) = 1 + 2 + 3 = 6$。
这是一个交互式问题。
欢迎，决斗者们！在这个交互式挑战中，存在一个未知整数 $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" |
你需要用最多 $\mathbf{4}$ 条指令使 $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"。
注意回答指令不计入 $\mathbf{4}$ 条指令的限制。
如果你的程序对一个测试用例发送超过 $\mathbf{4}$ 条指令或发送无效指令，裁判将返回"-1"。收到此响应后，你的程序应立即终止以避免被判错误答案。
在打印指令后，请勿忘记换行并刷新输出缓冲区，否则会因空闲超时被判失败。具体操作如下：
- C++：使用
- Java：使用
- Python：使用
- Rust：使用
- 其他语言请参考文档。
交互器是非自适应的。未知整数 $x$ 在交互过程中不会改变。
### Hack 格式
要进行 hack，请使用以下格式：
第一行包含一个整数 $t$（$1 \leq t \leq 5000$）——测试用例数量。
每个测试用例的第一行包含两个正整数 $n$ 和 $x$（$1 \leq n,x \leq 10^9$）——分别表示目标值和未知整数的初始值。
每个测试用例的第一行也是唯一一行包含一个整数 $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"。
注意回答指令不计入 $\mathbf{4}$ 条指令的限制。
如果你的程序对一个测试用例发送超过 $\mathbf{4}$ 条指令或发送无效指令，裁判将返回"-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$）——分别表示目标值和未知整数的初始值。
输入输出样例
输入 #1
2 100 0 1 1 1 5 1 1 1
输出 #1
add -10 add 1 mul 10 ! digit div 2 !
说明/提示
**解释**
$\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 完成
$\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 完成