CF2109C2.Hacking Numbers (Medium Version)

This is the medium version of the problem. In this version, you can send at most $\mathbf{4}$ commands. You can make hacks only if all versions of the problem are solved.

This is an interactive problem.

Welcome, Duelists! In this interactive challenge, there is an unknown integer $x$ ($1 \le x \le 10^9$). You must make it equal to a given integer in the input $n$. By harnessing the power of "Mathmech" monsters, you can send a command to do one of the following:

Command

Constraint

Result

Case

Update

Jury's response

"add $y$"

$-10^{18} \le y \le 10^{18}$

$\mathrm{res} = x + y$

$\text{if } 1 \le \mathrm{res} \le 10^{18}$

$x \leftarrow \mathrm{res}$

"1"

$\mathrm{else}$

$x \leftarrow x$

"0"

"mul $y$"

$1 \le y \le 10^{18}$

$\mathrm{res} = x \cdot y$

$\text{if } 1 \le \mathrm{res} \le 10^{18}$

$x \leftarrow \mathrm{res}$

"1"

$\mathrm{else}$

$x \leftarrow x$

"0"

"div $y$"

$1 \le y \le 10^{18}$

$\mathrm{res} = x/y$

$\text{if } y$ divides $x$

$x \leftarrow \mathrm{res}$

"1"

$\mathrm{else}$

$x \leftarrow x$

"0"

"digit"

—

$\mathrm{res} = S(x)$$^{\text{∗}}$

—

$x \leftarrow \mathrm{res}$

"1"

You have to make $x$ equal to $n$ using at most $\mathbf{4}$ commands.

$^{\text{∗}}$$S(n)$ is a function that returns the sum of all the individual digits of a non-negative integer $n$. For example, $S(123) = 1 + 2 + 3 = 6$

这是该题目的中等难度版本。在此版本中，你最多可以发送 $\mathbf{4}$ 条指令。仅当该题所有难度版本均已被解决时，你才可进行 Hack。

这是一道交互式问题。

欢迎各位决斗者！在此交互式挑战中，存在一个未知整数 $x$（满足 $1 \le x \le 10^9$）。你需要通过操作使其等于输入中给定的整数 $n$。借助“数学机械”（Mathmech）怪兽的力量，你可以发送以下四种指令之一：

指令	约束条件	结果	情况	更新	评测机响应
"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$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first and only line of each test case contains one integer $n$ ($1 \le n \le 10^9$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 5000$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n \le 10^9$）。

Solution

Jury

Explanation

$\texttt{2}$

There are 2 test cases.

$\texttt{100}$

In the first test case, the unknown integer $x = 9$ and we have to make it equal to $n = 100$.

$\texttt{add -10}$

$\texttt{0}$

The answer to "add -10" is "0". This means that the addition command was not successful as $x + y = 9 + (-10) \le 0$, and $x$ remains $9$ after the command

$\texttt{add 1}$

$\texttt{1}$

The answer to "add 1" is "1". This means that the addition command was successful as $x + y = 9 + 1 = 10$, and $x$ changes to $10$ after the command.

$\texttt{mul 10}$

$\texttt{1}$

The answer to "mul 10" is "1". This means that the multiplication command was successful as $x \cdot y = 10 \cdot 10 = 100$, and $x$ changes to $100$ after the command.

$\texttt{!}$

$\texttt{1}$

The answer to "!" is "1". This means you have determined that $x$ equals $n$.

$\texttt{5}$

In the second test case, the unknown integer $x = 1234$ and we have to make it equal to $n = 5$.

$\texttt{digit}$

$\texttt{1}$

The answer to "digit" is "1". This means that $x$ turned into the sum of its digits $1 + 2 + 3 + 4 = 10$, and $x$ changes to $10$ after the command.

$\texttt{div 2}$

$\texttt{1}$

The answer to "div 2" is "1". This means that the division command was successful as $y = 2$ is a divisor of $x = 10$, and $x$ changes to $\frac{x}{y} = \frac{10}{2} = 5$ after the command.

$\texttt{!}$

$\texttt{1}$

The answer to "!" is "1". This means you have determined that $x$ equals $n$.

Note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction.

解答

裁判组

解释

$\texttt{2}$

共有 2 个测试用例。

$\texttt{100}$

在第一个测试用例中，未知整数 $x = 9$，我们需要使其等于 $n = 100$。

$\texttt{add -10}$

$\texttt{0}$

对命令 “add -10” 的响应是 “0”。这表示加法操作失败，因为 $x + y = 9 + (-10) \le 0$，执行该命令后 $x$ 仍为 $9$。

$\texttt{add 1}$

$\texttt{1}$

对命令 “add 1” 的响应是 “1”。这表示加法操作成功，因为 $x + y = 9 + 1 = 10$，执行该命令后 $x$ 变为 $10$。

$\texttt{mul 10}$

$\texttt{1}$

对命令 “mul 10” 的响应是 “1”。这表示乘法操作成功，因为 $x \cdot y = 10 \cdot 10 = 100$，执行该命令后 $x$ 变为 $100$。

$\texttt{!}$

$\texttt{1}$

对命令 “!” 的响应是 “1”。这表示你已确认 $x$ 等于 $n$。

$\texttt{5}$

在第二个测试用例中，未知整数 $x = 1234$，我们需要使其等于 $n = 5$。

$\texttt{digit}$

$\texttt{1}$

对命令 “digit” 的响应是 “1”。这表示 $x$ 被替换为其各位数字之和 $1 + 2 + 3 + 4 = 10$，执行该命令后 $x$ 变为 $10$。

$\texttt{div 2}$

$\texttt{1}$

对命令 “div 2” 的响应是 “1”。这表示除法操作成功，因为 $y = 2$ 是 $x = 10$ 的一个约数，执行该命令后 $x$ 变为 $\frac{x}{y} = \frac{10}{2} = 5$。

$\texttt{!}$

$\texttt{1}$

对命令 “!” 的响应是 “1”。这表示你已确认 $x$ 等于 $n$。

注意：示例输入与输出中的空行仅为增强可读性，在实际交互中不会出现。