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 < 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.

N/A

N/A

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.