ВУЗ:
Составители:
Рубрика:
0
Технические требования:
Входной файл: INPUT.TXT содержит число [0..9].
Выходной файл: OUTPUT.TXT должен содержать единственное число – решение задачи.
Задача 7 (5 баллов) ("Минимальное покрытие")
Среди заданного множества отрезков прямой с целочисленными координатами концов [Li, Ri] не-
обходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0, M], где М
– натуральное число.
Ограничения: 1≤М≤5000; |Li|, |Ri|≤5000; I≤10000.
В первой строке входного файла INPUT.TXT указана константа М. В последующих строках перечис-
лены пары чисел (L
i
, R
i
), каждая пара чисел начинается с новой строки. Числа в парах отделены друг от дру-
га одним или несколькими пробелами. Список завершается парой чисел (0, 0).
Программа должна формировать в первой строке выходного файла OUTPUT.TXT требуемое мини-
мальное число отрезков из исходного множества, необходимое для покрытия отрезка [0, M]. Далее дол-
жен следовать список покрывающего подмножества, упорядоченного по возрастанию координат левых
концов отрезка. Список отрезков выводится в том же формате, что и во входном файле INPUT.TXT, за-
вершающую пару (0, 0) выводить не следует.
Если покрытие отрезка (0, M) исходным множеством отрезков
(L
i
, R
i
) невозможно, то файл OUTPUT.TXT должен содержать единственную фразу "No solution".
П р и м е р ы входного и выходного файлов.
1) INPUT.TXT 2) INPUT.TXT
1 1
-1 0 -1 0
-5 -3 0 1
2 5 0 0
0 0
OUTPUT.TXT OUTPUT.TXT
No solution 1
0 1
Задача 8 (6 баллов)
На треугольном поле, устроенном так, как показано на рис. 17, клетки пронумерованы последова-
тельными натуральными числами от единицы до бесконечности.
Путешественнику требуется пройти из клетки с номером М в клетку с номером N. Путешественник
может попасть в соседние клетки только через ребра треугольников (не через вершины). Количество
ребер, которое ему нужно будет пересечь в пути, называется длиной маршрута.
Напишите программу, которая вычисляет длину кратчайшего маршрута для заданных точек М и N.
Во входном файле INPUT.TXT содержатся числа М и N, разделенные одним или несколькими про-
белами. Числа М и N – натуральные, не менее единицы и не более одного миллиарда.
Программа должна выдать в выходной файл OUTPUT.TXT длину кратчайшего пути из М в N.
П р и м е р ы входного и выходного файлов.
INPUT.TXT
Рис. 17
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
