← 返回题目列表

Codeforces · 1867/E1

E1. Salyg1n 和数组(简单版)

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

这是问题的简单版本。版本之间的唯一区别是查询数量的限制。在此版本中,您最多可以进行 100 条查询。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

这是一个交互问题!

salyg1n 给了你一个正整数 $$$k$$$ 并且想和你玩一个游戏。他选择了一个由 $$$n$$$ 整数组成的数组 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。您必须打印 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$,其中 $$$\oplus$$$ 表示按位异或运算。您可以进行以下类型的查询:

- $$$?$$$ $$$i$$$:响应此查询,您将收到 $$$a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$$$。另外,在这个查询之后,子数组 $$$a_i, a_{i + 1}, \ldots, a_{i + k - 1}$$$ 将被反转,即所选数组 $$$a$$$ 将变为: $$$a_1, a_2, \ldots a_{i - 1}, a_{i + k - 1}, a_{i + k - 2}, \ldots, a_{i + 1}、a_i、a_{i + k}、\ldots、a_n$$$。

您只能进行不超过 $$$100$$$ 的查询来回答该问题。

输入

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

互动

你的程序和陪审团程序之间的交互首先读取两个正偶数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq k^2 \leq 2500$$$) – 分别是所选数组的长度和查询子数组的长度。

要查找 $$$a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$$$ 的值,请以 $$$?$$$ $$$i$$$ ($$$1 \leq i \leq n - k + 1$$$) 格式打印查询。然后读取一个整数——您的查询的答案。

您最多可以进行 $$$100$$$ 查询。当您准备好打印答案时,以 $$$!$$$ $$$x$$$ 格式输出。之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。打印答案不算作 $$$100$$$ 查询之一。

如果您的程序对一组输入数据进行超过 $$$100$$$ 查询,或者进行无效查询,则对该查询的响应将为 -1。收到这样的响应后,您的程序应立即终止以接收“错误答案”的判决。否则,它可能会收到任何其他判决。

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

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客:

要执行黑客攻击,请使用以下格式:

第一行包含一个整数 $$$t$$$ – 测试用例的数量。

每个测试用例的描述应由两行组成。第一行包含数字 $$$n$$$ 和 $$$k$$$ – 分别是所选数组的长度和查询子数组的长度。第二行包含 $$$n$$$ 数字 $$$a_1, a_2, \ldots, a_n$$$ – 陪审团应为此测试用例选择的数组。

示例

输入 #1

2
4 2

6

4

6 6

4

输出 #1

? 1

? 3

! 2

? 1

! 4

注意

在第一个测试用例中,陪审团选择了数组 $$$a$$$ $$$=$$$ $$$[4, 2, 5, 1]$$$

在第二个测试用例中,陪审团选择了数组 $$$a$$$ $$$=$$$ $$$[5, 7, 1, 3, 3, 7]$$$