← 返回题目列表

Codeforces · 2109/C1

C1. 黑客号码(简单版)

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

这是问题的简单版本。在此版本中,您最多可以发送 $$$\mathbf{7}$$$ 命令。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

这是一个交互问题。

欢迎,决斗者!在此交互式挑战中,有一个未知整数 $$$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"

你必须使 $$$x$$$ 等于 $$$n$$$ 使用 最多 $$$\mathbf{7}$$$ 命令。

$$$^{\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" 否则。

请注意回答 不算数 达到 $$$\mathbf{7}$$$ 命令的限制。

如果您的程序为一个测试用例发出超过 $$$\mathbf{7}$$$ 命令,或者发出无效命令,则对该命令的响应将为 "-1"。收到这样的响应后,你的程序应该立即终止以接收判决 错误答案。否则,它可能会收到任何其他判决。

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

  • fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
  • System.out.flush() ;
  • 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}$$$答案 “第 2 部分” is "1"。这意味着除法命令成功,因为 $$$y = 2$$$ 是 $$$x = 10$$$ 的除数,并且命令执行后 $$$x$$$ 更改为 $$$\frac{x}{y} = \frac{10}{2} = 5$$$。
$$$\texttt{!}$$$$$$\texttt{1}$$$答案 "!" is "1"。这意味着您已确定 $$$x$$$ 等于 $$$n$$$。

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