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

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

HotLog


 

Автобус

(Время: 2 сек. Память: 32 Мб Сложность: 47%)

Каждое утро Антон едет на работу на автобусе. Маршрут автобуса включает в себя N остановок, пронумерованных от 1 до N в порядке следования. Автобус проезжает от каждой остановки до следующей за одну минуту, а его временем стоянки можно пренебречь. Антон садится на первой остановке и выходит на последней.

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

Когда человек входит в автобус, он садится на ближайшее от входа свободное сиденье. Если они все заняты, он ищет ближайшее от входа сиденье, рядом с которым никто не стоит, и встаёт у сидящего там человека над душой. Если такого места нет, он выходит из автобуса.

Каждый пассажир остаётся на своём месте до прибытия на нужную ему остановку. Стоящий пассажир остаётся стоять, даже если какое-то сиденье освободилось.

На каждой остановке из автобуса сначала выходят все пассажиры, которые собирались выйти на этой остановке, и только потом заходят новые.

Антон зашёл в автобус первым, он может сесть на любое сиденье и остаться на нём до конца поездки. Он хорошо знает, кто ещё будет ехать в автобусе, про каждого пассажира Антон знает, на какой остановке тот войдет в автобус и на какой выйдет. Помогите Антону выбрать место так, чтобы во время поездки у него как можно меньше суммарно стояли над душой.

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

В первой строке входного файла INPUT.TXT заданы три целых числа N, M и K – количество остановок, количество сидений в автобусе и количество пассажиров, кроме Антона (2 ≤ N ≤ 109, 1 ≤ M, K ≤ 2×105).

В следующих K строках задано по 2 числа ai и bi, которые означают, что i-й пассажир собирается войти на ai-й остановке и выйти на bi-й (1 ≤ ai < bi ≤ n).

Если на одной остановке в автобус заходит несколько человек, они заходят в том порядке, в котором они перечислены во входных данных.

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

В выходной файл OUTPUT.TXT выведите два числа на одной строке – минимальное суммарное время в минутах, в течение которого у Антона будут стоять над душой, и номер места, на которое для этого нужно сесть. Если таких мест несколько, выведите ближайшее место от входа.

Пример

INPUT.TXTOUTPUT.TXT
110 2 3
1 10
3 9
7 10
3 2

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Перестановки
 Структуры данных
 Библиотека алгоритмов
 A. Полка
 B. Баланс скобок
 C. Строки
 D. Строки - 2
 E. Голосование
 F. Студенты
 G. Легион
 H. Коммерческий калькулятор
 I. Забор
 J. Силовые поля
 K. Автобус
 L. Трамвай

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



https://si-save-invest-otzyvy.ru si save.