Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Минимальное покрытие

На прямой задано некоторое множество отрезков с целочисленными координатами концов [Li, Ri]. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок [0, M], (M — натуральное число), содержащее наименьшее число отрезков.
 
Входные данные
В первой строке указана константа M (1<=M<=5000). В каждой последующей строке записана пара чисел Li и Ri (|Li|,|Ri| < 50000), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.
 
Выходные данные
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка [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

https://informatics.msk.ru/moodle/mod/statements/view.php?chapterid=3356#


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: