E. notepad.exe
binary search; constructive algorithms; greedy; interactive
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 < a_2 < \ldots < 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 < \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.
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\).
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.