Solved by 98 users: ...
UserDateAttemptTimeCMSC
zhuojie`27 dec 2008`Python312.7268
MasterYoda`07 oct 2009`C++2300.0591
fetetriste`07 dec 2008`C++300.0692
MasterYoda`07 oct 2009`C++2100.0593
MasterYoda`07 oct 2009`C++2000.0594
DAV`07 oct 2009`C++1700.0496
Philip_PV`30 jul 2008`C++1000.0297
DAV`07 oct 2009`C++1600.0497
DAV`07 oct 2009`C++1500.0498
MasterYoda`07 oct 2009`C++1900.0598
Philip_PV`30 jul 2008`C++900.0299
DAV`07 oct 2009`C++1400.04101
MasterYoda`07 oct 2009`C++1800.05104
fetetriste`07 dec 2008`C++200.06108
Philip_PV`30 jul 2008`C++800.02109
Philip_PV`30 jul 2008`C++700.02111
rajivmathews`13 nov 2006`C++400.05115
tomek`10 apr 2006`C++200.05117
ravehanker`06 sep 2006`C++400.15117
tttttt`31 mar 2012`C++800.04118
RAVEman`31 dec 2008`C++400.02121
 C++ 75 Kylix 11 FPC 7 Java 2 C 2 Ruby 1 Python 1
` >  >  >  >  >  >  >  >  >  > `

## Alise and Basilio

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" n1 times, "2" — n2 times, ..., "i" — n_i times, n1 + n2 + .. + 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 n1, n2, ... 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#1```4 10 10 10 10 ``` Output#1```80 ```
 Input#2```2 1 1 ``` Output#2```2 ```
 Input#3```3 99 1 1 ``` Output#3```103 ```
 Input#4```3 0 0 1 ``` Output#4```0 ```
 Input#5```3 0 1 1 ``` Output#5```2 ```

Author:
Moscow contest 2004 (MSU, 17 november 2004, http://acm.msu.ru/2002/10/moscow-2002-b.pdf)
15 October 2003

 © acm.mipt DevGroupThe page was generated in 190ms