A16822 | $Flatten or Concatenate$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是一个交互题。 在工作中摸鱼的时候，妖精 Dilhan 偶然发现了两个数组 $a$ 和 $b$。最开始，它们都只包含一个整数 $2^k$（即 $a=b=[2^k]$），其中 $k$ 是一个非负整数。 Dilhan 随后对这两个数组进行了任意次数（可能为零），任意顺序的如下两种操作： 1. 扁平化（Flatten）—— 选择 $a$ 或 $b$ 中的一个数组，在数组中任选一个当前最大的元素 $x$（$x$ 不要求在另一个数组中也为最大）。然后，将 $x$ 替换为在同一位置上的两个 $\frac x 2$。该操作只能在 $x$ 为偶数时进行。 2. 拼接（Concatenate）—— 令 $a$ 和 $b$ 都变为 $a+b$，其中 $+$ 表示数组拼接操作。 在若干操作之后，Dilhan 丢弃了 $b$，并将 $a$ 隐藏起来，向你发起了挑战。 记隐藏数组 $a$ 的长度为 $n$。你可以进行以下询问： - 选择一个区间 $[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}$，且该数组可由题目描述中的构造过程得到。 保证所有测试用例中 $n$ 之和不超过 $10^5$。

（交互题，请按照要求输出）

输入 #1

输出 #1

? 3 8

? 1 4

? 5 11

! 2

? 1 1

! 1

? 1 1

? 2 2

? 3 3

? 4 4

! 4

! 1073741824

C++ 编辑器

输入

输出