| 最终 Boss 第 2 阶段(熔岩)/ Giant Bowser — Shiho Fujii、Ryo Nagamatsu、新超级马里奥兄弟 Wii |
![]() |
这是问题的困难版本。版本之间的区别在于,在此版本中,$$$n \leq 400$$$ 并且您可以进行$$$1500$$$ 查询。只有解决了该问题的所有版本,您才能破解。
这是一个交互问题。
令 $$$n$$$ 为正整数。调用 $$$n$$$ 变量 $$$x_1, \ldots, x_n$$$ 上的函数 最小-最大 如果它可以被构造为仅写入 $$$\min$$$ 和 $$$\max$$$ 调用 $$$x_1, \ldots, x_n$$$ ,每个变量在表达式中按从左到右的顺序恰好出现一次。例如,$$$\min(x_1, x_2, x_3)$$$ 是 $$$3$$$ 变量上的最小-最大函数,但 $$$\max(\min(x_1, x_3), x_2)$$$ 和 $$$\min(\max(x_1, x_2), \max(x_2, x_3))$$$ 不是。
Bowser 在 $$$n$$$ ($$$2 \leq n \leq 400$$$) 变量上选择了最小-最大函数,并告诉您 $$$n$$$。此外,他还允许您提出以下形式的查询:您向 Bowser $$$n$$$ 整数 $$$x_1, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) 作为输入,他会告诉您 $$$f(x_1, \ldots, x_n)$$$。
要逃离他的城堡,你必须总共使用最多 $$$1500$$$ 查询来推断他的功能。之后,为了向他证明你已经学会了这个函数,Bowser 会给你最多 $$$5000$$$ 他自己的输入 $$$x_1, \ldots, x_n$$$,你必须用正确的值 $$$f(x_1, \ldots, x_n)$$$ 来响应。
由于Bowser的城堡非常安全,他实际上有多种功能供你弄清楚,总变量数最多为$$$400$$$。此外,他还限制您在所有函数中最多使用 $$$1500$$$ 查询,并且他总共不会提出超过 $$$5000$$$ 查询。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 200$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 400$$$) — min-max 函数中的变量数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$400$$$。
阅读此行输入后,交互将从您的第一个查询开始。
互动
要进行查询,请按以下格式输出一行(不带引号):
- "? $$$x_1$$$ $$$x_2$$$ $$$\ldots$$$ $$$x_n$$$" ($$$1 \leq x_i \leq 10^9$$$)。
然后,在每次查询后,读取一个整数——查询的答案。您最多可以进行 $$$1500$$$ 此类查询 所有 $$$t$$$ 测试用例的总计 。
一旦您准备好开始回答 Bowser 的查询,请输出包含单个字符的行“!“(不带引号)。
Bowser 的每个查询都包含一行 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) - Bowser 的输入。保证 Bowser 不会进行超过 $$$5000$$$ 查询 。
每次查询后,输出一个整数 - $$$f(x_1, x_2, \ldots, x_n)$$$ 的值。请注意,这些查询是 在线,因此 Bowser 只会在您回复上一个查询后才为您提供下一个查询。
Bowser 完成查询后,您将收到一行包含整数 $$$0$$$。之后,继续进行下一个测试用例,或者如果这是最后一个测试用例则退出。
此任务中的交互器是 部分自适应。特别是,Bowser 选择的功能在每次交互开始时都是固定的,但他向您提出的问题可能会发生变化。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,则您的解决方案必须立即退出。这意味着您的解决方案将获得 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
要破解,请使用以下格式。
第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 200$$$) — 测试用例的数量。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 400$$$) — min-max 函数中的变量数量。
每个测试用例的第二行应包含以下列表中的一系列空格分隔的标记(不带引号),指定 min-max 函数:
- "分钟"
- "最大"
- "("
- ")"
- ","
- $$$1, 2, \ldots, n$$$ 范围内的正整数。
所有测试用例的 $$$n$$$ 总和不应超过 $$$400$$$。
例如,示例输入对应的黑客案例如下:
2
3
max ( 1 , 2 , 3 )
4
min ( max ( 1 , 2 ) , max ( 3 , 4 ) )
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 3 5 2 3 6 2 3 5 7 0 4 8 3 8 7 6 5 0
输出复制
? 5 4 3 ? 1 2 1 ! 6 7 ? 1 9 8 7 ? 5 1000000000 2 3 ! 6
注意
在第一个测试用例中,Bowser 的最小-最大函数为 $$$f := \max(x_1, x_2, x_3)$$$。在提出两个查询以从评审团收到 $$$f(5, 4, 3) = 5$$$ 和 $$$f(1, 2, 1) = 2$$$ 后,解决方案就可以回答评审团的查询了。它正确推导出 $$$f(3, 6, 2) = 6$$$ 和 $$$f(3, 5, 7) = 7$$$。
在第二个测试用例中,Bowser 的最小-最大函数为 $$$f := \min(\max(x_1, x_2), \max(x_3, x_4))$$$。在提出两个查询以从评审团收到 $$$f(1, 9, 8, 7) = 8$$$ 和 $$$f(5, 10^9, 2, 3) = 3$$$ 后,该解决方案已准备好回答评审团的查询。它正确推导出 $$$f(8, 7, 6, 5) = 6$$$。
请注意,不保证示例中的查询唯一确定最小-最大函数。该示例仅用于演示查询如何工作。示例输入和输出中的空行只是为了更好的可读性;您不需要在解决方案中输出它们。
