这是一个交互问题。
文本编辑器中有 $$$n$$$ 个单词。第 $$$i$$$ 个单词的长度为 $$$l_i$$$ ($$$1 \leq l_i \leq 2000$$$)。数组 $$$l$$$ 是隐藏的,只有评分者知道。
文本编辑器按行显示单词,将每两个单词分成一行,至少有一个空格。请注意,一行不必以空格结尾。让文本编辑器的高度参考所使用的行数。对于给定的宽度,文本编辑器将以高度最小化的方式显示单词。
更正式地说,假设文本编辑器的宽度为 $$$w$$$。令 $$$a$$$ 为长度为 $$$k+1$$$ 的数组,其中 $$$1=a_1 < a_2 < \ldots < a_{k+1}=n+1$$$。如果对于所有 $$$1 \leq i \leq k$$$、$$$l_{a_i}+1+l_{a_i+1}+1+\ldots+1+l_{a_{i+1}-1} \leq w$$$,$$$a$$$ 是一个有效数组。那么文本编辑器的高度是所有有效数组中的最小值$$$k$$$。
请注意,如果 $$$w < \max(l_i)$$$,则文本编辑器无法正确显示所有单词并会崩溃,并且文本编辑器的高度将为 $$$0$$$。
您可以提出 $$$n+30$$$ 查询。在一个查询中,您提供宽度 $$$w$$$。然后,当宽度为 $$$w$$$ 时,评分器将返回文本编辑器的高度 $$$h_w$$$。
求文本编辑器的最小区域,即 $$$w \cdot h_w$$$ 在所有 $$$w$$$ 中的最小值,其中 $$$h_w \neq 0$$$。
长度是预先固定的。换句话说,交互器不具有适应性。
输入
输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 文本编辑器上的单词数。
保证隐藏长度 $$$l_i$$$ 满足 $$$1 \leq l_i \leq 2000$$$。
互动
通过阅读 $$$n$$$ 开始交互。
要进行查询,请打印“? $$$w$$$”(不带引号,$$$1 \leq w \leq 10^9$$$)。然后您应该从标准输入读取我们的响应,即 $$$h_w$$$。
如果您的程序进行了无效查询或已用完尝试次数,则交互器将立即终止,并且您的程序将得到错误答案。
要给出最终答案,请打印“!$$$area$$$”(不带引号)。请注意,给出此答案不计入 $$$n+30$$$ 查询的限制。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
输入的第一行必须包含单个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 文本编辑器中的单词数。
输入的第二行必须恰好包含 $$$n$$$ 空格分隔的整数 $$$l_1,l_2,\ldots,l_n$$$ ($$$1 \leq l_i \leq 2000$$$)。
示例
输入 #1
6 0 4 2
输出 #1
? 1 ? 9 ? 16 ! 32
注意
在第一个测试用例中,单词是 $$$\{\texttt{glory},\texttt{to},\texttt{ukraine},\texttt{and},\texttt{anton},\texttt{trygub}\}$$$,所以 $$$l=\{5,2,7,3,5,6\}$$$。
如果$$$w=1$$$,则文本编辑器无法正确显示所有单词并且会崩溃。文本编辑器的高度为$$$h_1=0$$$,因此评分器将返回$$$0$$$。
如果$$$w=9$$$,则单词在文本编辑器上显示的可能方式是:
- $$$\texttt{荣耀__to}$$$
- $$$\texttt{乌克兰__}$$$
- $$$\texttt{and_anton}$$$
- $$$\texttt{__trygub_}$$$
文本编辑器的高度为 $$$h_{9}=4$$$,因此评分器将返回 $$$4$$$。
如果$$$w=16$$$,则单词在文本编辑器上显示的可能方式是:
- $$$\texttt{荣耀_to_ukraine}$$$
- $$$\texttt{and_anton_trygub}$$$
文本编辑器的高度为 $$$h_{16}=2$$$,因此评分器将返回 $$$2$$$。
我们以某种方式发现文本编辑器的最小区域是$$$32$$$,所以我们回答它。