tw-tw
Сообщений: 126
Оценки: 0
Присоединился: 2005-03-07 23:20:49
|
Помогите решить такую задачу. Тем кто не хоче или не может просьба не флудить.
Среди заданного множества отрезков прямой с целочисленными координатами концов [ Li , Ri ] необходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0,M], где M – натуральное число.
Ограничения: 1 £ M £ 5000; | Li |, | Ri | £ 50000; i £ 100000.
Входные данные
В первой строке входного файла INPUT.TXT указана константа M. В последующих строках перечислены пары чисел “Li Ri” , каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами. Список завершается парой чисел “0 0”.
Выходные данные
Программа должна формировать в первой строке выходного файла OUTPUT.TXT требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0,M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входном файле INPUT.TXT, завершающую пару [0,0] выводить не следует.
Если покрытие отрезка [0,M] исходным множеством отрезков [Li,Ri] невозможно, то файл OUTPUT.TXT должен содержать единственную фразу “No solution”.
Во входном файле такие данные(для примера)
INPUT.TXT
1
-1 0
-5 –3
2 5
0 0
Или такие
INPUT.TXT
1
-1 0
0 1
0 0
Все кто поможет огромное спасибо
|
Задача на Паскале - 
