<ПРЕД Задача:
СЛЕД>
Задачу решили 98 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Алиса и Базилио

Time limit = 3 секунд(ы)

Алиса и Базилио, чтобы скоротать время до нового клиента, играют в игру: Алиса загадывает число от 1 до N, а Базилио пытается его отгадать. Они договорились, что Базилио может задавать только вопросы вида

"Принадлежит ли число заданному множеству X?"

на которые Алиса отвечает либо "да", либо "нет".

Алиса всегда играет так, что в серии из K последовательных загадываний каждое из чисел 1, 2, ... N встречается ровно n_i раз (хотя и в разном порядке). К сожалению, у Базилио короткая память, и он не может запомнить даже преды- дущее число, загаданное Алисой, а писать он не умеет, хотя читать его научили. Мальвина, движимая странной симпатией к Базилио, однажды подслушала всю серию из K загадываний и выписала, сколько раз встречается каждое число i.

Она отдала эту бумажку Базилио.

Не могли бы Вы помочь Базилио найти минимальное количество вопросов, которое он в худшем случае должен задать Алисе в каждой серии из K загадываний, чтобы угадать все числа. Как было сказано, Базилио не в состоянии запомнить или записать предыдущие ответы Алисы. Когда Базилио точно знает, какое число загадала Алиса, он называет это число, и это не считается вопросом.

Вход Первая строка на стандартном потоке ввода содержит целое число N (1 ≤ N ≤ 10000). Последующие N строк содержат целые числа c_i — количество появлений числа i (списано с бумажки Мальвины). Каждое число удовлетворяет ограничению 0 ≤ c_i ≤ 100000.

Выход На стандартный поток вывода напечатайте минимальное количество вопросов, требующееся Базилио, чтобы угадать все числа в серии.

Вход#1
4
10
10
10
10
Выход#1
80

Вход#2
2
1
1
Выход#2
2

Вход#3
3
99
1
1
Выход#3
103

Вход#4
3
0
0
1
Выход#4
0
Вход#5
3
0
1
1
Выход#5
2

Автор:
Московская олимпиада, МГУ, 17 ноября 2002 года
15 октября 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 3.81.28.10