Московская городская олимпиада школьников по информатике,
2004/05 учебный год
при поддержке компании
Задача Y. Троллейбусы
| Имя входного файла: | y.in |
| Имя выходного файла: | y.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Троллейбусы одного маршрута проходят через остановку каждые k (1≤k≤500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем.
Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0до k--1), чтобы:
- Суммарное время ожидания троллейбуса для всех пассажиров было минимально.
- Максимальное из времен ожидания троллейбуса было минимально.
Формат входных данных
Во входном файле записано сначала число k, затем - число N (0≤N≤100000). Затем идет N чисел, задающих времена прихода пассажиров на остановку. Каждое из этих чисел - целое от 0 до 100000.
Формат выходных данных
В выходной файл запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно. Если решений несколько, выведите любое из них.
Пример
| y.in | y.out |
100 5 0 210 99 551 99 |
10 51 |