|
Угадай высоту
(Время: 1 сек. Память: 32 Мб Сложность: 80%)
У Алексея младшая сестра Аня любит строить башенку из кубиков. Как-то Аня решила похвалиться брату какую большую башню она собрала и даже показала брату свои записи на листе бумаги. Алексей увидел список чисел и спросил, что эти числа значат. Тогда Аня начала объяснять: «Первое число N – сколько кубиков в башенке было сначала, а дальше K чисел – это сколько кубиков я добавляла или убирала». Алексей спросил: «А как понять, когда добавляла, а когда убирала?» Аня улыбнулась и убежала. Алексей, зная высоту комнаты в кубиках (H), в которой Аня строила башенку, задумался, а какая минимальная и максимальная возможная высота башенки могла быть в конечном счёте?
Входные данные
Входной файл INPUT.TXT содержит в первой строке три целых числа H, N, K (0 ≤ H, N ≤ 109; 1 ≤ K ≤ 40). Во второй строке записаны K натуральных чисел – количество кубиков, которое Аня добавила или убрала с башенки. Гарантируется, что существует корректная последовательность изменений высоты башенки.
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа – минимальную и максимальную возможную высоту башенки в конечном счёте.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 12 4 4
5 6 2 3 | 2 8 |
Пояснение к примеру
Сначала у нас диапазон кубиков [0; 12]. Кубиков было 4.
На первом изменении = 5, получим -1 или 9, но -1 кубиков не может быть, поэтому 9 кубиков.
На втором изменении = 6, получим 3 или 15, но 15 кубиков не может быть, поэтому 3 кубика.
На третьем изменении = 2, получим 1 или 5.
На четвёртом изменении = 3, получим -2, 4, 2, 8, но -2 кубиков не может быть, поэтому минимальное число кубиков равно 2, а максимальное равно 8.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
