CF1672E.notepad.exe

This is an interactive problem.

There are $n$ words in a text editor. The $i$-th word has length $l_i$ ($1 \leq l_i \leq 2000$). The array $l$ is hidden and only known by the grader.

The text editor displays words in lines, splitting each two words in a line with at least one space. Note that a line does not have to end with a space. Let the height of the text editor refer to the number of lines used. For the given width, the text editor will display words in such a way that the height is minimized.

More formally, suppose that the text editor has width $w$. Let $a$ be an array of length $k+1$ where $1=a_1 \lt a_2 \lt \ldots \lt a_{k+1}=n+1$. $a$ is a valid array if for all $1 \leq i \leq k$, $l_{a_i}+1+l_{a_i+1}+1+\ldots+1+l_{a_{i+1}-1} \leq w$. Then the height of the text editor is the minimum $k$ over all valid arrays.

Note that if $w \lt \max(l_i)$, the text editor cannot display all the words properly and will crash, and the height of the text editor will be $0$ instead.

You can ask $n+30$ queries. In one query, you provide a width $w$. Then, the grader will return the height $h_w$ of the text editor when its width is $w$.

Find the minimum area of the text editor, which is the minimum value of $w \cdot h_w$ over all $w$ for which $h_w \neq 0$.

The lengths are fixed in advance. In other words, the interactor is not adaptive.

这是一个交互式问题。

文本编辑器中有 $n$ 个单词。第 $i$ 个单词的长度为 $l_i$（$1 \leq l_i \leq 2000$）。数组 $l$ 是隐藏的，仅评测机知晓。

文本编辑器将单词按行显示，同一行中相邻两个单词之间至少用一个空格分隔（注意：一行末尾不一定有空格）。定义文本编辑器的高度为所使用的行数。对于给定的宽度 $w$，文本编辑器将以使高度最小的方式显示所有单词。

更形式化地，假设文本编辑器的宽度为 $w$。令 $a$ 是一个长度为 $k+1$ 的数组，满足 $1=a_1 \lt a_2 \lt \ldots \lt 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 \lt \max(l_i)$，则文本编辑器无法正常显示全部单词，将会崩溃，此时其高度定义为 $0$。

你最多可进行 $n+30$ 次查询。每次查询中，你提供一个宽度 $w$，评测机会返回当编辑器宽度为 $w$ 时对应的高度 $h_w$。

请找出文本编辑器的最小面积，即对所有满足 $h_w \neq 0$ 的 $w$，求 $w \cdot h_w$ 的最小值。

所有单词长度在交互开始前即已固定（即交互器是非自适应的）。

The first and only line of input contains a single integer $n$ ($1 \leq n \leq 2000$) — the number of words on the text editor.

It is guaranteed that the hidden lengths $l_i$ satisfy $1 \leq l_i \leq 2000$.

输入仅有一行，包含一个整数 $n$（$1 \leq n \leq 2000$）—— 表示文本编辑器中单词的数量。

保证隐藏的长度 $l_i$ 满足 $1 \leq l_i \leq 2000$。

In the first test case, the words are ${\texttt{glory},\texttt{to},\texttt{ukraine},\texttt{and},\texttt{anton},\texttt{trygub}}$, so $l={5,2,7,3,5,6}$.

If $w=1$, then the text editor is not able to display all words properly and will crash. The height of the text editor is $h_1=0$, so the grader will return $0$.

If $w=9$, then a possible way that the words will be displayed on the text editor is:

• \texttt{glory__to}
• \texttt{ukraine__}
• \texttt{and_anton}
• \texttt{__trygub_}

The height of the text editor is $h_{9}=4$, so the grader will return $4$.

If $w=16$, then a possible way that the words will be displayed on the text editor is:

• \texttt{glory_to_ukraine}
• \texttt{and_anton_trygub}

The height of the text editor is $h_{16}=2$, so the grader will return $2$.

We have somehow figured out that the minimum area of the text editor is $32$, so we answer it.

在第一个测试用例中，单词为 ${\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$，因此输出该值。