← 返回题目列表

Codeforces · 2246/E

E. lce4113 和安全游戏

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

这是一个交互问题。 此外,针对此问题禁用了黑客攻击。

有两个隐藏整数 $$$b$$$ 和 $$$v$$$ 使得 $$$b \in \{0,1\}$$$ 和 $$$0 \le v \lt 2^{30}.$$$ 还有一个隐藏运算 $$$\mathrm{ty},$$$ 可以是 $$$\&$$$ 或 $$$|.$$$ 这里, $$$\&$$$ 表示按位与运算。另外,$$$|$$$表示按位或运算。

你的目标是猜测 $$$b.$$$

交互过程如下:

  • 首先,将值 $$$x$$$ 发送到交互器,使得 $$$0 \le x \lt 2^{30}$$$。
  • 交互器发回 $$$v\,\mathrm{ty}\,x$$$。正式地,它将发回 $$$o(v,x)$$$,其中 $$o(v,x) = \begin{cases}v\,\&\,x & \mathrm{ty} = \& \\ v\,|\,x & \mathrm{ty} = |.\end{cases}$$
  • 然后发送两个数字 $$$m_0$$$ 和 $$$m_1$$$,其中 $$$0 \le m_0, m_1 \lt 2^{30}.$$$
  • 最后,交互器将发送回$$$m_b \oplus v,$$$,其中$$$\oplus$$$表示按位异或运算。

交互后,你要输出$$$b$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。请注意,这是给出的唯一初始输入。

互动

首先,您需要输出一个整数 $$$x \, (0 \le x \lt 2^{30})$$$ — 发送给交互器的初始值。

作为响应,您将收到一个整数 $$$o\,(0 \le o \lt 2^{30})$$$ — $$$v\,\mathrm{ty}\,x.$$$ 运算的结果 $$$o(v,x)$$$

接下来,您将发送一行包含两个整数 $$$m_0, m_1\,(0 \le m_0, m_1 \lt 2^{30}).$$$

最后,接收一个整数 $$$r\,(0 \le r \lt 2^{30})$$$ — $$$m_b \oplus v.$$$ 的值

请注意,交互器是 部分自适应 — 特别是, $$$v$$$ 的选择可以由初始输入 $$$x$$$ 决定,但是 所有隐藏值将在之后修复.

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

$$$^{\text{*}}$$$要刷新,请使用:

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

示例

输入
复制

3

0

315

3

35

5

5

输出
复制

2

314 159

0

3

12 34

1

0

0 0

1

注意

示例交互过程如下:

解决方案互动者说明
$$$3$$$有 $$$3$$$ 测试用例。
$$$2$$$解决方案选择 $$$x = 2$$$。
$$$0$$$交互器发回 $$$x\,\mathrm{ty}\,v = 2\,\&\,1 = 0.$$$
$$$314$$$ $$$159$$$解决方案发送 $$$m_0 = 314$$$ 和 $$$m_1 = 159.$$$
$$$315$$$交互者响应 $$$m_b \oplus v = m_0 \oplus v = 315.$$$
$$$0$$$解确定 $$$b = 0.$$$
$$$3$$$下一个测试用例开始。解决方案选择 $$$x = 3$$$。
$$$3$$$交互器发回 $$$x\,\mathrm{ty}\,v = 3\,|\,1 = 3.$$$
$$$12$$$ $$$34$$$解决方案发送 $$$m_0 = 12$$$ 和 $$$m_1 = 34.$$$
$$$35$$$交互者响应 $$$m_b \oplus v = m_1 \oplus v = 35.$$$
$$$1$$$解确定 $$$b = 1.$$$
$$$0$$$最终测试用例开始。解决方案选择 $$$x = 0$$$。
$$$5$$$交互器发回 $$$x\,\mathrm{ty}\,v = 0\,|\,5 = 5.$$$
$$$0$$$ $$$0$$$解决方案发送 $$$m_0 = 0$$$ 和 $$$m_1 = 0.$$$
$$$5$$$交互者响应 $$$m_b \oplus v = m_1 \oplus v = 5.$$$
$$$1$$$解确定 $$$b = 1.$$$

请注意,示例解决方案进行的查询可能无法产生足够的信息来确定隐藏位 $$$b.$$$ 此外,示例交互中的空行是为了可读性而给出的,不需要在解决方案中输出。

测试用例中的隐藏值如下所示。

测试#$$$v$$$$$$b$$$$$$\mathrm{ty}$$$
$$$1$$$$$$1$$$$$$0$$$$$$\&$$$
$$$2$$$$$$1$$$$$$1$$$$$$|$$$
$$$3$$$$$$5$$$$$$1$$$$$$|$$$