这是问题的简单版本。版本之间的唯一区别是查询数量的限制。在此版本中,您最多可以进行 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]$$$