Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
Time limit = 3 second(s)
Alice and Basilio play game untill a new person to be fooled come along.Alice chooses an integer number from the set {1, 2, ..., N} and Basilio should guess it. He can ask any questions which imply answer "YES" or "NO".
N maybe very great (1 < = N < = 10000) and Basilio have to ask too many questions.
Malvina is a good, educated girl, erudite, she knows mathematics, information theory, a set of programming languages and etc. Filled with sympathy to Basilio she decided to help him. She knows that Alice next K times will choose "1" n_{1} times, "2" — n_{2} times, ..., "i" — n_i times, n_{1} + n_{2} + .. + n_N = K (but the order in which Alice will choose it is unknown). Using this information she writes program that helps Basilio to minimize number of questions (it provides algorithm of asking questions).
This program is restarted each time Alise chooses a number. So this program has no information about previous Alise's numbers.
Do you know what is the maximum possible number of questions which may ask this program?
Show you do.
Input The first line contains N (1 ≤ N ≤ 10000 ). Next N lines contain numbers n_{1}, n_{2}, ... n_N. (0 ≤ n_i ≤ 100000)
Output Integer number M — minimum number of questions, whitch will be sufficient to guess all K numbers ( whatever order Alice choose). It means the following: there is algorithm of asking questions to Alice, that allow to guess all K numbers after less than M, or equal to M, questions. But for any m < M it is not the case.
Input#14 10 10 10 10 |
Output#180 |
Input#22 1 1 |
Output#22 |
Input#33 99 1 1 |
Output#3103 |
Input#43 0 0 1 |
Output#40 |
Input#53 0 1 1 |
Output#52 |
Author:
Moscow contest 2004 (MSU, 17 november 2004, http://acm.msu.ru/2002/10/moscow-2002-b.pdf)
15 October 2003
© acm.mipt DevGroup The page was generated in 210ms |