← 返回题目列表

Codeforces · 2178/E

E. 展平或连接

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

这是一个交互问题。

在工作拖延时,精灵 Dilhan 偶然发现了两个数组 $$$a$$$ 和 $$$b$$$。最初,它们都由单个整数 $$$2^k$$$ 组成(即 $$$a=b=[2^k]$$$),其中 $$$k$$$ 是非负整数。

Dilhan 然后以任意顺序应用以下两种类型的操作任意次数(可能为零):

  1. 展平 — 选择 $$$a$$$ 或 $$$b$$$,然后选择 任何 元素 $$$x$$$ 即 最大 在该数组中($$$x$$$ 确实 不 需要在另一个数组中最大)。然后,在同一位置将 $$$x$$$ 替换为 $$$\frac x2$$$ 的两个副本。仅当 $$$x$$$ 为偶数时才能应用此操作。
  2. 连接 — 设置 两者 $$$a$$$ 和 $$$b$$$ 为 $$$a+b$$$,其中 $$$+$$$ 表示数组串联。

执行这些操作后,Dilhan 会丢弃 $$$b$$$,对你隐藏 $$$a$$$,并向你发起游戏挑战。

令 $$$n$$$ 为隐藏数组 $$$a$$$ 的长度。您可以进行以下查询:

  • 选择一个区间 $$$[l, r]$$$ ($$$1\le l\le r\le n$$$),Dilhan 会告诉你总和 $$$a_l+a_{l+1}+\cdots+a_r$$$。

通过进行最多 $$$300$$$ 查询来确定 $$$a$$$ 的最大元素的值。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — $$$a$$$ 的长度。

保证$$$1\le a_i\le 2^{30}$$$,并且可以通过语句中描述的过程生成数组$$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

互动

对于每个测试用例,首先给您一个整数 $$$n$$$ — 隐藏数组 $$$a$$$ 的长度。然后您最多可以进行 $$$300$$$ 查询。

要进行查询,请按以下格式打印一行:

  • $$$\texttt{?}\;l\;r$$$ ($$$1\le l\le r\le n$$$) — 为查询选择的索引。

打印查询后,交互器将返回一个整数 - 总和 $$$a_l+a_{l+1}+\ldots+a_r$$$。

要报告您已确定 $$$a$$$ 的最大元素的值,请按以下格式打印您的答案:

  • $$$\texttt{!}\; m$$$ ($$$1\le m\le 2^{30}$$$) — 最大元素的值。

打印答案不算作 $$$300$$$ 查询之一。

打印答案后,继续下一个测试用例。如果当前测试用例是最后一个,则终止程序。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

这个问题中的交互者是 不 自适应。换句话说,数组 $$$a$$$ 在任何查询之前都是固定的,并且在交互过程中不会改变。

在此问题中,黑客被禁用。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

4
11

9

4

12

1

1

8

4

4

4

4

8

输出
复制


? 3 8

? 1 4

? 5 11

! 2

? 1 1

! 1

? 1 1

? 2 2

? 3 3

? 4 4

! 4

! 1073741824

注意

在第一个测试用例中,Dilhan 的隐藏数组 $$$a$$$ 是 $$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$。它可以通过以下过程生成:

#类型操作后$$$a$$$操作后$$$b$$$
0$$$[4]$$$$$$[4]$$$
1压平$$$a$$$$$$[\下划线 4] \到 {[2, 2]}$$$$$$[4]$$$
2压平$$$b$$$$$$[2, 2]$$$$$$[\下划线 4] \到 {[2, 2]}$$$
3压平$$$a$$$$$$[2, \下划线 2] \到 {[2, 1, 1]}$$$$$$[2, 2]$$$
4连接$$$[2, 1, 1, 2, 2]$$$$$$[2, 1, 1, 2, 2]$$$
5压平$$$a$$$$$$[\下划线 2, 1, 1, 2, 2]\到 {[1, 1, 1, 1, 2, 2]}$$$$$$[2, 1, 1, 2, 2]$$$
6连接$$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$$$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$
  • 对于查询$$$\mathtt{?\;3\;8}$$$,陪审团回答$$$1+1+2+2+2+1=9$$$;
  • 对于查询$$$\mathtt{?\;1\;4}$$$,陪审团回答$$$1+1+1+1=4$$$;
  • 对于查询$$$\mathtt{?\;5\;11}$$$,陪审团的回答是$$$2+2+2+1+1+2+2=12$$$。

$$$a$$$ 的最大元素值为$$$2$$$。

在第二个测试用例中,数组 $$$a$$$ 只有一个元素。通过查询,唯一元素的值为$$$1$$$,而且也一定是最大值。

在第三个测试用例中,Dilhan 的隐藏数组 $$$a$$$ 是 $$$[4, 4, 4, 4, 4, 4, 4, 4]$$$。它可以通过以下过程生成:

#类型操作后$$$a$$$操作后$$$b$$$
0$$$[4]$$$$$$[4]$$$
1连接$$$[4, 4]$$$$$$[4, 4]$$$
2连接$$$[4, 4, 4, 4]$$$$$$[4, 4, 4, 4]$$$
3连接$$$[4, 4, 4, 4, 4, 4, 4, 4]$$$$$$[4, 4, 4, 4, 4, 4, 4, 4]$$$

而$$$a$$$的最大元素值为$$$4$$$。

在第四个测试用例中,Dilhan 的隐藏数组 $$$a$$$ 为 $$$[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$$$。