← 返回题目列表

Codeforces · 2077/B

B. 求或求和

中文机器翻译题面 查看原题
改变自我 - Yuta Imai vs Qlarabelle

这是一个交互问题。

有两个隐藏的非负整数 $$$x$$$ 和 $$$y$$$ ($$$0 \leq x, y \lt 2^{30}$$$)。您最多可以提出以下形式的 $$$2$$$ 查询。

  • 选择一个非负整数 $$$n$$$ ($$$0 \leq n \lt 2^{30}$$$)。法官将返回 $$$(n \mathbin{|} x) + (n \mathbin{|} y)$$$ 的值,其中 $$$|$$$ 表示按位或运算。

之后,法官会给你另一个非负整数$$$m$$$ ($$$0 \leq m \lt 2^{30}$$$)。您必须回答 $$$(m \mathbin{|} x) + (m \mathbin{|} y)$$$ 的正确值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

互动

选择两个隐藏整数 $$$x$$$ 和 $$$y$$$ ($$$0 \leq x, y \lt 2^{30}$$$)。请注意,对于不同的测试用例,$$$x$$$ 和 $$$y$$$ 可能不同。

此任务中的交互器是 不自适应。换句话说,整数$$$x$$$和$$$y$$$在交互过程中不会改变。

要提出查询,请选择一个整数 $$$n$$$ ($$$0 \leq n \lt 2^{30}$$$) 并仅将整数 $$$n$$$ 打印到一行。

您将收到一个整数,即 $$$(n \mathbin{|} x) + (n \mathbin{|} y)$$$ 的值。

您最多可以使用以下形式进行 $$$2$$$ 查询。

查询完成后,输出“!”一行。您将收到一个整数 $$$m$$$ ($$$0 \leq m \lt 2^{30}$$$)。请注意,$$$m$$$ 的值在交互之前也是固定的。

您必须在一行中仅输出 $$$(m \mathbin{|} x) + (m \mathbin{|} y)$$$ 的值。请注意,这一行是 不 被认为是一个查询,并且是 不 在计算询问的数量时考虑在内。

此后,继续下一个测试用例。

如果您在交互过程中进行超过 $$$2$$$ 查询,您的程序必须立即终止,并且您将收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

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

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • System.out.flush() 在 Java 中;
  • 冲洗(输出) 帕斯卡;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

要破解,请遵循以下测试格式。

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含三个整数 $$$x, y, m$$$ ($$$0 \leq x, y, m \lt 2^{30}$$$)。

示例

输入
复制

2

3

4

1

0

1

输出
复制

0

1

!

4

0

!

2

注意

在第一个测试中,交互进行如下。

解决方案评审团说明
$$$\texttt{2}$$$有 2 个测试用例。
$$$\texttt{}$$$在第一个测试用例中,$$$x=1$$$ 和 $$$y=2$$$。
$$$\texttt{0}$$$$$$\texttt{3}$$$解决方案要求 $$$(0 \mathbin{|} 1) + (0 \mathbin{|} 2)$$$,陪审团以 $$$3$$$ 回应。
$$$\texttt{1}$$$$$$\texttt{4}$$$解决方案要求 $$$(1 \mathbin{|} 1) + (1 \mathbin{|} 2)$$$,陪审团以 $$$4$$$ 回应。
$$$\texttt{!}$$$$$$\texttt{1}$$$解决方案请求 $$$m$$$ 的值,陪审团以 $$$1$$$ 响应。
$$$\texttt{4}$$$由于之前的查询,解决方案知道 $$$(1 \mathbin{|} x) + (1 \mathbin{|} y)=4$$$ 。
$$$\texttt{}$$$在第二个测试用例中,$$$x=0$$$ 和 $$$y=0$$$。
$$$\texttt{0}$$$$$$\texttt{0}$$$解决方案要求 $$$(0 \mathbin{|} 0) + (0 \mathbin{|} 0)$$$,陪审团以 $$$0$$$ 回应。
$$$\texttt{!}$$$$$$\texttt{1}$$$解决方案请求 $$$m$$$ 的值,陪审团以 $$$1$$$ 响应。
$$$\texttt{2}$$$该解决方案以某种方式推断出 $$$x=y=0$$$,因此它响应 $$$(1 \mathbin{|} 0) + (1 \mathbin{|} 0)=2$$$。

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