CF1672E notepad.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$。 请你求出文本编辑器的最小面积，即所有 $h_w \neq 0$ 的 $w \cdot h_w$ 的最小值。 单词长度在测试开始前就已确定。也就是说，交互器不是自适应的。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示文本编辑器中的单词数。 保证隐藏的长度 $l_i$ 满足 $1 \leq l_i \leq 2000$。

首先读入 $n$。 每次询问时，输出 "? $w$"（不含引号，$1 \leq w \leq 10^9$）。然后你应从标准输入读取我们的回复，即 $h_w$。 如果你的程序进行了非法的询问或超出了询问次数限制，交互器会立即终止，你的程序会得到 Wrong answer 的判定。 最终输出答案时，输出 "! $area$"（不含引号）。注意，输出最终答案不计入 $n+30$ 次询问限制。 每次输出询问后不要忘记换行并刷新输出缓冲区，否则会得到 Idleness limit exceeded 的判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hacks 输入的第一行必须是一个整数 $n$（$1 \leq n \leq 2000$），表示文本编辑器中的单词数。 输入的第二行必须是 $n$ 个用空格分隔的整数 $l_1,l_2,\ldots,l_n$（$1 \leq l_i \leq 2000$）。

在第一个测试用例中，单词为 $\{\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{glory\_\_to}$ - $\texttt{ukraine\_\_}$ - $\texttt{and\_anton}$ - $\texttt{\_\_trygub\_}$ 此时高度 $h_9=4$，评测器会返回 $4$。 如果 $w=16$，文本编辑器可能的显示方式为： - $\texttt{glory\_to\_ukraine}$ - $\texttt{and\_anton\_trygub}$ 此时高度 $h_{16}=2$，评测器会返回 $2$。 假设我们已经求出文本编辑器的最小面积为 $32$，则输出答案。 由 ChatGPT 4.1 翻译