notepad.exe

题意翻译

这是一道交互题。 在文本编辑器里有 $n$ 个单词，其中第 $i$ 个单词的长度为 $l_i$ ($1 \le l_i \le 2000$)。$l$ 仅对测评机可见。 文本编辑器一行一行展示文本，以空格分开相邻的两个单词，但是行末不一定有空格，即单词可以直接作为某一行的末尾。定义文本的高度 $h$ 为文本展示需要的行数。对于给定的屏幕宽度，编辑器会以高度最小的方式显示。 更正式地，设文本编辑器的宽度为 $w$ 。设 $a$ 是一个长度为 $k + 1$ 的序列，其中 $1 = a_1 < a_2 < ... < a_{k+1} = n + 1$. $\{a_n\}$ 是一个合法的序列当且仅当，$\forall 1 \le i \le k, l_{a_i} + 1 + l_{a_{i + 1}} + 1 + \dots + 1 + l_{a_{i+1} - 1} \le w$。 那么，$h$ 就是所有合法的 $\{a_n\}$ 中最小的 $k$. 注意，如果 $w \le \max(l_i)$，那么文本编辑器将不能显示所有的文字并且崩溃，此时 $h = 0$ . 你可以做 $n + 30$ 次询问。每次询问中，输出宽度 $w$ . 测评机将返回 $h_w$ ，即当宽度为 $w$ 的最小高度、 请找到文本编辑器的最小面积，即求 $min(w\times h_w | 1 \le w \le n)$.

题目描述

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

输出格式

Begin the interaction by reading $ n $ . To make a query, print "? $ w $ " (without quotes, $ 1 \leq w \leq 10^9 $ ). Then you should read our response from standard input, that is, $ h_w $ . If your program has made an invalid query or has run out of tries, the interactor will terminate immediately and your program will get a verdict Wrong answer. To give the final answer, print "! $ area $ " (without the quotes). Note that giving this answer is not counted towards the limit of $ n+30 $ queries. After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks The first line of input must contain a single integer $ n $ ( $ 1 \leq n \leq 2000 $ ) — the number of words in the text editor. The second line of input must contain exactly $ n $ space-separated integers $ l_1,l_2,\ldots,l_n $ ( $ 1 \leq l_i \leq 2000 $ ).

输入输出样例

输入样例 #1

6

0

4

2

输出样例 #1

? 1

? 9

? 16

! 32

说明

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.