← 返回题目列表

Codeforces · 1672/E

E. 记事本.exe

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

这是一个交互问题。

文本编辑器中有 $$$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$$$,所以我们回答它。