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

Минимальное число шагов

Time limit = 5 секунд

Пете для организации олимпиады по программированию нужно преодолеть бюрократический барьер, а именно, пройти через N кабинетов, получая либо тратя в каждом какие-то деньги.

Но Петя может заплатить 100 монет за то, чтобы пропустить следующий кабинет, либо 200 монет, чтобы пропустить следующие два кабинета, и вообще дать взятку в размере 100*k монет, за то, чтобы пропустить следующие k инстанций.

Перед входом в первый кабинет у него 0 монет. У Пети не может быть отрицательного количества монет.

Помогите Пете — напишите програму, которая находит оптимальный способ "давания взяток" и выводит минимальное количество инстанций. Заметьте, что первую и последнюю инстанцию нужно пройти обязательно.

Вход В первой строчке количество кабинетов N (1 ≤ N ≤ 1000 ). Во второй строчке N целых чисел по модулю меньше 10000. Положительные числа означают, что в соответствующем кабинете вы получаете деньги, а отрицательные — отдаете.

Выход Выведите -1, если невозможно преодолеть бюрократический барьер. Если его можно продолеть, то выведите минимальное количество инстанций, где придётся побывать Пете.

Вход#1
1
100
Выход#1
1
Вход#2
1
-20
Выход#2
-1
Вход#3
4
120 20 20 20
Выход#3
3
Вход#4
6
30 30 30 30 30 30
Выход#4
5


Автор:
Ворожцов Артем
27 сентября 2003

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


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

SW soft NIX
ID = 3.95.139.100