这是一个运行两次(通信)交互问题。
有两个玩家:玩家A和玩家B。陪审团(也称为该问题的交互者)将首先与玩家A进行交互。玩家A结束交互后,陪审团将与玩家B进行交互。注意,玩家A和玩家B不能直接向对方传递信息;两名玩家只能向陪审团发送信息或从陪审团接收信息。
在互动之前,陪审团确定一个整数 $$$n$$$ 以及从 $$$1$$$ 到 $$$n$$$ 的整数的排列 $$$p$$$$$$^{\text{∗}}$$$ 一次。这些价值观对于两名球员来说是一致的。
玩家 A 从陪审团处收到 $$$n$$$ 的值以及 $$$p$$$ 的所有元素。然后,玩家A必须向陪审团发送一个二进制整数$$$x$$$(即$$$x$$$必须等于$$$0$$$或$$$1$$$)。
玩家 B 从陪审团处收到 $$$n$$$ 的值和整数 $$$x$$$(与玩家 A 发送的整数相同)。然而,排列$$$p$$$并没有提供给玩家B。玩家B的任务是确定整数$$$n$$$在$$$p$$$中的位置。为此,玩家 B 可以通过以下形式向陪审团提出最多 $$$30$$$ 查询:
- 选择任意两个整数 $$$l$$$ 和 $$$r$$$ ($$$l \leq r$$$),陪审团将回复 $$$\max(p_{l}, p_{l+1}, \ldots, p_{r}) - \min(p_{l}, p_{l+1}, \ldots, p_{r})$$$。
玩家 A 希望确保玩家 B 能够确定 $$$n$$$ 的位置。你的任务是扮演两个玩家,并为两个玩家确定最佳交互策略,以便玩家 B 正确确定 $$$n$$$ 的位置。
第一次运行
您的代码将在每个测试中运行两次。第一次运行时,您将成为玩家 A。
输入
输入的第一行包含字符串 第一。这样做的目的是让您的程序认识到这是它的第一次运行,并且它应该充当玩家 A。
输入的第二行恰好包含一个整数 $$$t$$$ — 测试用例的数量 ($$$1 \le t \le 100$$$)。
第 $$$i$$$ 个测试用例的第一行包含一个整数 $$$n$$$ — 第 $$$i$$$ 个测试用例的 $$$p$$$ 的长度 ($$$2 \le n \le 10^4$$$)。
第 $$$i$$$ 个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$p_1, p_2, \ldots, p_n$$$。保证该序列形成排列。
保证所有测试用例的$$$n$$$总和不超过$$$10^4$$$。
输出
对于每个测试用例,在新行上打印一个整数 $$$x$$$,$$$0$$$ 或 $$$1$$$。这是第二次运行时发送给您的整数。
此后,继续进行下一个测试用例,或者如果它是最后一个测试用例,则终止程序。
第二次运行
在第二轮中,您是玩家 B。
输入
输入的第一行包含字符串 第二。这样做的目的是让您的程序认识到这是它的第二次运行,并且它应该充当玩家 B。
输入的第二行恰好包含一个整数 $$$t$$$ — 测试用例的数量 ($$$1 \le t \le 100$$$)。请注意,该数字等于第一次运行输入中的 $$$t$$$。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$2 \leq n \leq 10^4$$$, $$$0 \leq x \leq 1$$$)。这表示 $$$p$$$ 的长度以及玩家 A 在上次运行中发送的二进制整数 $$$x$$$。
请注意,第二次运行中的测试用例可能会被打乱。请参阅示例测试用例以获取更多说明。
互动
对于第 $$$i$$$ 个测试用例,请记住,根据上述输入格式,您将首先在陪审团的输入中收到 $$$n$$$ 和 $$$x$$$。收到这些输入后,您最多可以进行以下形式的 $$$30$$$ 查询(忽略引号):
- ?左 ($$$1 \leq l \leq r \leq n$$$)。
每次查询后,陪审团将响应 $$$\max(p_{l}, p_{l+1}, \ldots, p_{r}) - \min(p_{l}, p_{l+1}, \ldots, p_{r})$$$,您应该在其中阅读输入流。
如果您的程序进行超过 $$$30$$$ 查询,您的程序应立即终止以接收判决 错误答案。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
一旦您准备好报告 $$$n$$$ 的位置,您可以按照以下格式进行操作:
- !磷 ($$$1 \leq P \leq n$$$),其中 $$$P$$$ 是 $$$n$$$ 的位置。
然后,您将继续执行下一个测试用例,或者如果您已处理完每个测试用例,则程序必须终止。
交互器是 不 自适应。也就是说,排列在交互过程中不会改变,并且始终与第一次运行时显示的排列相同。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{†}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
first 3 3 3 2 1 5 1 2 3 4 5 5 4 2 3 5 1
输出复制
0 0 1
输入复制
second 3 3 0 2 1 1 5 1 2 5 0 4 0
输出复制
? 1 3 ? 1 2 ? 2 3 ! 1 ? 1 2 ! 4 ? 1 5 ? 5 5 ! 5
注意
第一次运行:给出排列 $$$[3,2,1]$$$、$$$[1,2,3,4,5]$$$、$$$[4,2,3,5,1]$$$。根据玩家之间的某种策略,分别发送整数$$$0$$$、$$$0$$$和$$$1$$$。
第二次运行:请注意,测试用例在运行之间会重新排序。这次,排列按 $$$[3,2,1]$$$、$$$[4,2,3,5,1]$$$、$$$[1,2,3,4,5]$$$ 的顺序给出。但是,请注意,每个测试用例的整数 $$$x$$$ 与第一次运行中给出的整数相同(即 $$$0,1,0$$$)。
考虑第二次运行的第一个排列。排列为 $$$p = [3, 2, 1]$$$。
在第一个查询中,玩家 B 询问 $$$p_1, p_2, p_3$$$ 之间的最大值和最小值之间的差。法官的答案是$$$2$$$($$$p = [3, 2, 1]$$$,因此$$$\max(p_1, p_2, p_3) - \min(p_1, p_2, p_3) = 3 - 1 = 2$$$)。
同样,对于玩家 B 提出的第二个和第三个问题,法官都以 $$$1$$$ 回答。然后,玩家 B 使用他所做的查询以及玩家 A 选择的整数,计算出整数 $$$n$$$ ($$$n = 3$$$) 可以在排列的位置 $$$1$$$ 处找到。这是正确的,因为 $$$p_1 = 3$$$。