← 返回题目列表

Codeforces · 2109/C3

C3. 黑客号码(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。在此版本中,语句中描述了您可以发送的命令的限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

这是一个交互问题。

欢迎,决斗者!在此交互式挑战中,有一个未知整数 $$$x$$$ ($$$1 \le x \le 10^9$$$)。您必须使其等于输入 $$$n$$$ 中的给定整数。通过利用“Mathmech”怪物的力量,您可以发送命令来执行以下操作之一:

命令约束结果案例更新陪审团的回应
“添加$$$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{其他}$$$$$$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{其他}$$$$$$x \leftarrow x$$$"0"
“div $$$y$$$”$$$1 \le y \le 10^{18}$$$$$$\mathrm{res} = x/y$$$$$$\text{if } y$$$ 除 $$$x$$$$$$x \leftarrow \mathrm{res}$$$"1"
$$$\mathrm{其他}$$$$$$x \leftarrow x$$$"0"
“数字”—$$$\mathrm{res} = S(x)$$$$$$^{\text{*}}$$$—$$$x \leftarrow \mathrm{res}$$$"1"

设 $$$f(n)$$$ 为最小整数,使得存在一系列 $$$f(n)$$$ 命令,将所有 $$$x(1 \le x \le 10^9)$$$ 将 $$$x$$$ 转换为 $$$n$$$。您事先并不知道 $$$x$$$ 的值。找到$$$f(n)$$$,这样无论$$$x$$$是什么,你总是可以使用最多$$$f(n)$$$命令将其转换为$$$n$$$。

您的任务是将 $$$x$$$ 更改为 $$$n$$$ 使用 最多 $$$f(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$$$ 开始。

要发送命令,请按以下格式输出一行:

  • “添加$$$y$$$” 将一些整数 $$$y$$$ ($$$-10^{18} \le y \le 10^{18}$$$) 添加到 $$$x$$$。

    评审团将输出 "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}$$$。

  • “数字” 使 $$$x$$$ 等于其数字之和。

    陪审团将始终输出 "1" 并更新$$$x \leftarrow S(x)$$$。

请注意,命令是 区分大小写.

当确定 $$$x$$$ 等于 $$$n$$$ 时,按以下格式输出一行:

  • "!" — 陪审团将输出 "1" 如果 $$$n$$$ 等于 $$$x$$$,并且 "-1" 否则。

请注意回答 不算数 朝着你的命令限制。

如果您的程序为一个测试用例生成了多个 $$$f(n)$$$ 命令($$$f(n)$$$ 如上所述),或者生成了无效命令,则对该命令的响应将为 "-1"。收到这样的响应后,你的程序应该立即终止以接收判决 错误答案。否则,它可能会收到任何其他判决。

打印命令后,不要忘记输出行尾并刷新输出。否则,你会得到 超出空闲限制。为此,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • System.out.flush() 在 Java 中;
  • sys.stdout.flush() 在 Python 中;
  • std::io::stdout().flush() Rust 中的 ;
  • 请参阅其他语言的文档。

交互器是 非自适应。未知整数$$$x$$$ 没有改变 在互动过程中。

黑客

要破解,请使用以下格式。

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。

每个测试用例的第一行应包含两个正整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n,x \leq 10^9$$$) — 分别表示未知整数和应使其相等的目标值。

示例

输入
复制

2
100

0

1

1

1

5

1

1

1

输出
复制

add -10

add 1

mul 10

!

digit

div 2

!

注意

解决方案评审团说明
$$$\texttt{2}$$$有 2 个测试用例。
$$$\texttt{100}$$$在第一个测试用例中,未知整数 $$$x = 9$$$,我们必须使其等于 $$$n = 100$$$。
$$$\texttt{添加-10}$$$$$$\texttt{0}$$$的答案 “添加-10” is "0"。这意味着加法命令不成功,因为 $$$x + y = 9 + (-10) \le 0$$$,并且命令后 $$$x$$$ 仍然是 $$$9$$$
$$$\texttt{添加 1}$$$$$$\texttt{1}$$$的答案 “加1” is "1"。这意味着加法命令成功,$$$x + y = 9 + 1 = 10$$$,命令后$$$x$$$ 更改为$$$10$$$。
$$$\texttt{mul 10}$$$$$$\texttt{1}$$$的答案 “乘10” is "1"。这意味着乘法命令成功,为 $$$x \cdot y = 10 \cdot 10 = 100$$$,命令后 $$$x$$$ 更改为 $$$100$$$。
$$$\texttt{!}$$$$$$\texttt{1}$$$的答案 "!" is "1"。这意味着您已确定 $$$x$$$ 等于 $$$n$$$。
$$$\texttt{5}$$$在第二个测试用例中,未知整数 $$$x = 1234$$$,我们必须使其等于 $$$n = 5$$$。
$$$\texttt{数字}$$$$$$\texttt{1}$$$的答案 “数字” is "1"。这意味着 $$$x$$$ 变为其数字之和 $$$1 + 2 + 3 + 4 = 10$$$,并且 $$$x$$$ 在命令之后变为 $$$10$$$。
$$$\texttt{div 2}$$$$$$\texttt{1}$$$的答案 “div 2” is "1"。这意味着除法命令成功,因为 $$$y = 2$$$ 是 $$$x = 10$$$ 的除数,并且命令执行后 $$$x$$$ 更改为 $$$\frac{x}{y} = \frac{10}{2} = 5$$$。
$$$\texttt{!}$$$$$$\texttt{1}$$$的答案 "!" is "1"。这意味着您已确定 $$$x$$$ 等于 $$$n$$$。

请注意,示例输入和输出中的空行是为了清楚起见,在实际交互中不会出现。