Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.03.2010, 18:13
гость

 
Сообщений: n/a

Мобильный оператор
Время телефонного разговора состоит из N частей. Первые N-1 частей имеют длительности Ki минут, и каждая минута из i-й части стоит Ei. Последняя часть имеет бесконечную длительность, и каждая минута этой части стоит En. Все части идут последовательно, т.е. сразу после завершения i-й части начинается часть i+1. Тарификация поминутная, т.е. деньги снимаются в начале каждой минуты за всю минуту целиком. Если у абонента не хватает денег на разговор в следующей минуте, разговор обрывается.

Нужно найти максимальную общую длину разговора (в минутах) при наличии M денег. Возможно делать несколько звонков.

Входные данные:
В первой строке два целых числа N, M.
В следуюзей строке задано N-1 чисел, которые соответствуют длительностям Ki.
Далее идут N чисел, которые соответствуют стоимостям Ei.

Выходные данные:
Одно число - макс. количество минут.

Ограничения:
1 <= N <= 77,
1 <= M, Ki, Ei <= 1000000 (10^6)
вермя 5 с, память 64 мб

Пример ввода:
2 10
5
1 2

Пример вывода:
10

ссылка на задачу:
http://acm.lviv.ua/fusion/viewpage.p...=4bae12109087b
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра