ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Минимальное покрытие

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Среди заданного множества отрезков прямой с целочисленными координатами концов [Li, Ri] необходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0, M], где M – целое положительное число.

Исходные данные

В первой строке записано целое число M (1 ≤ M ≤ 5000). В последующих строках перечислены пары целых чисел Li и Ri (−50000 ≤ Li < Ri ≤ 50000), каждая пара с новой строки, числа в парах отделены друг от друга одним пробелом. В последней строке записана пара нулей. Множество содержит не менее одного и не более 99999 отрезков.

Результат

Программа должна формировать в первой строке требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0, M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe, завершающую пару нулей выводить не следует.
Если покрытие отрезка [0, M] исходным множеством отрезков [Li, Ri] невозможно, то следует вывести единственную фразу «No solution».

Примеры

исходные данныерезультат
1
-1 0
-5 -3
2 5
0 0
No solution
1
-1 0
0 1
0 0
1
0 1
Источник задачи: II Командный студенческий чемпионат Урала по программированию. Екатеринбург, 3-4 апреля 1998 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1303. Минимальное покрытие