<PREV Problem:
NEXT>
Solved by 98 users: ...
UserDateAttemptTimeCMSC
zhuojie27 dec 2008Python312.7268 
MasterYoda07 oct 2009C++2300.0591 
fetetriste07 dec 2008C++300.0692 
MasterYoda07 oct 2009C++2100.0593 
MasterYoda07 oct 2009C++2000.0594 
DAV07 oct 2009C++1700.0496 
Philip_PV30 jul 2008C++1000.0297 
DAV07 oct 2009C++1600.0497 
DAV07 oct 2009C++1500.0498 
MasterYoda07 oct 2009C++1900.0598 
Philip_PV30 jul 2008C++900.0299 
DAV07 oct 2009C++1400.04101 
MasterYoda07 oct 2009C++1800.05104 
fetetriste07 dec 2008C++200.06108 
Philip_PV30 jul 2008C++800.02109 
Philip_PV30 jul 2008C++700.02111 
rajivmathews13 nov 2006C++400.05115 
tomek10 apr 2006C++200.05117 
ravehanker06 sep 2006C++400.15117 
tttttt31 mar 2012C++800.04118 
RAVEman31 dec 2008C++400.02121 
Languages
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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 18.207.106.142