Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Акции

(Время: 1 сек. Память: 16 Мб Сложность: 28%)

Корпорация «Buy & Sell» для привлечения денежных средств в свой бизнес выпустила акции, цена которых ежедневно изменялась в течении N дней.

Василий Петрович, имея в наличии сумму в размере S рублей, решил на этом заработать и в один из дней купил акции на всю сумму (в результате покупки у него могла остаться сумма, меньшая стоимости одной акции), а затем в этот или в один из последующих дней, он продал все акции.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральные числа N и S – количество дней и стартовая сумма. Вторая строка содержит N натуральных чисел Ai – цены одной акции с 1-го по N-й день. Все числа во входных данных не превышают 105.

Выходные данные

В выходной файл OUTPUT.TXT выведите два целых числа, разделенных пробелом: искомую минимальную и максимальную возможную сумму.

Примеры

INPUT.TXTOUTPUT.TXT
15 100
17 14 11 20 15
70 181
25 10
1 2 3 4 5
10 50

Пояснения к примерам

В первом примере наименее прибыльно купить 5 акций в первый день (15+5*17=100) и продать их в третий день (15+5*11=70). Наиболее выгодно акции покупать в третий день (1+9*11=100) и продать их в четвертый день (1+9*20=181).

Во втором примере наихудшим вариантом будет служить тот, когда покупка и продажа протекают в один и тот же день. Наилучший исход – это покупка в первый день, а продажа – в последний.

Система оценки

Решения, работающие только для N = 5, будут оцениваться в 20 баллов.

Решения, работающие только для N ≤ 1000, будут оцениваться в 60 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Высота треугольника
 B. Болото
 C. ДНК-палиндром
 D. Сыграешь с Денисом?
 E. Акции
 F. Сказочная страна
 G. Hello world!
 H. Гонки

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru