Департамент образования г.Москвы
МГУ им.М.В.Ломоносова
МИОО
МЦНМО
ДНТТМ

Московская олимпиада по информатике

на сайте www.olympiads.ru

Новости Об олимпиаде Личная олимпиада Командная олимпиада Пробный интернет-тур Заочный тур Сборы Странички других лет www.olympiads.ru
Тренировочный интернет-тур
О туре, задачи, тесты
Регистрация, изменение настроек
Страница сдачи решений
Текущие результаты
FAQ по работе с тестирующей системой
Несколько советов участникам олимпиад
Задать вопрос оргкомитету

Московская городская олимпиада школьников по информатике, 2004/05 учебный год
при поддержке компании
NIX

Задача 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
Webmaster: webmaster@olympiads.ru