ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин.

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

В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.

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

Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.

Пример входного файла

4
1 2
1 3
2 3
2 4

Пример выходного файла

2
1 2 4
3

   Решение

Задачи

Страница: << 1 2 3 4 >> [Всего задач: 17]      



Задача 102894  (#11)

 [Считай путем ]
Тема:   [ Представление графов в памяти ]
Сложность: 3

Задан ориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая подсчитывает количество различных путей между всеми парами вершин графа.

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

Входной файл содержит количество вершин графа N (1 ≤ N ≤ 33) и список дуг графа, заданных номерами начальной и конечной вершин.

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

Вывести в выходной файл матрицу N × N, элемент (i, j) которой равен числу различных путей, ведущих из вершины i в вершину j, или -1, если существует бесконечно много таких путей.

Пример входного файла

5
1 2
2 4
3 4
4 1
5 3
1 1

Пример выходного файла

-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 1 -1 0
Прислать комментарий     Решение


Задача 102895  (#12)

 [Игра в города ]
Тема:   [ Эйлеров цикл ]
Сложность: 3

Всем известны правила игры «в города»: первый игрок называет произвольный город, следующий – город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных. Задан список допустимых для описанной игры слов, слова в нем могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз, сколько оно в нем встречается.

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

В первой строке входного файла записано целое число N – количество слов в списке (1 ≤ N ≤ 1000), а в последующих N строках – сами слова. Каждое из них является последовательностью не более чем из 10 строчных английских букв. 

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

Выведите в выходной файл слова в искомом порядке, либо сообщение «NO», если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.

Пример входного файла

4
b
ab
bc
bb

Пример выходного файла

ab
bb
b
bc
Прислать комментарий     Решение


Задача 102896  (#13)

 [Открытки и конверты ]
Тема:   [ Паросочетания ]
Сложность: 4

Жюри решило поздравить авторов метода Форда-Фалкерсона, алгоритмов Флойда-Беллмана, Кнута-Морриса-Пратта, формы Бэкуса-Науэра, схемы Ривеста-Шамира-Адлемана и других классиков Computer Science с наступающим 4 июля (Днем независимости). Для этого было куплено N открыток и M конвертов. К сожалению, конверты и открытки оказались разных размеров, и некоторые открытки помещаются не во все конверты. Напишите программу, находящую такое распределение открыток по конвертам, при котором поздравления получат наибольшее число классиков Computer Science. В один конверт разрешается вкладывать не более одной открытки. 

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

В первой строке входного файла записаны числа M и N (0 ≤ M, N ≤ 100). Далее записаны высота и ширина каждого из M конвертов, затем – высота и ширина каждой из N открыток. Размеры конвертов и открыток являются натуральными числами, не превосходящими 32767, и разделяются пробелами и/или символами перевода строки.

Выходные данные
Выведите в выходной файл целое число K – максимальное количество открыток, которые можно разложить по конвертам. Далее выведите K пар целых чисел, означающих номер открытки и номер конверта, в который ее необходимо положить.

Пример входного файла

4 4
3 3 141 282 282 141 200 100
3 1 140 280 141 282 201 1

Пример выходного файла

4
1 1 2 3 3 2 4 4
Прислать комментарий     Решение


Задача 102897  (#14)

 [Покрытие путями ]
Тема:   [ Паросочетания ]
Сложность: 3+

Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин.

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

В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.

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

Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.

Пример входного файла

4
1 2
1 3
2 3
2 4

Пример выходного файла

2
1 2 4
3
Прислать комментарий     Решение


Задача 102898  (#15)

 [Поможем МПС ]
Тема:   [ Потоки ]
Сложность: 4

В некоторой стране протянута сеть железных дорог. Требуется наладить сообщение между двумя различными городами A и B, пустив наибольшее возможное число поездов от A до B. Из-за конструктивных особенностей поездов, нарушений расписания и прочих объективных причин необходимо, чтобы никакие два поезда не проезжали через один город, за исключением,
конечно, городов A и B.

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

В первой строке входного файла записаны целое число M – количество городов в стране (2 ≤ M ≤ 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.

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

Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.

Пример входного файла

5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5

Пример выходного файла

2
2 1 4
2 3 4
Прислать комментарий     Решение


Страница: << 1 2 3 4 >> [Всего задач: 17]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .