Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
>>
глава 3. Алгоритмы на графах
Фильтр
Задачи
Страница: << 1 2 3 4 >> [Всего задач: 17]
Задан ориентированный граф с 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
Всем известны правила игры «в города»: первый игрок называет произвольный
город, следующий – город, название которого начинается на ту же букву, на
которую заканчивается название предыдущего города, и т.д. Аналогичным
образом можно играть не в названия городов, а, например, в названия
животных.
Задан список допустимых для описанной игры слов, слова в нем могут
повторяться. Напишите программу, определяющую, в каком порядке в процессе
игры должны быть названы слова из списка, чтобы каждое слово было
использовано ровно столько раз, сколько оно в нем встречается.
Входные данные
В первой строке входного файла записано целое число N – количество слов в списке (1 ≤ N ≤ 1000), а в последующих N строках – сами слова. Каждое из них является последовательностью не более чем из 10 строчных английских букв.
Выходные данные
Выведите в выходной файл слова в искомом порядке, либо сообщение «NO», если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.
Пример входного файла
4
b
ab
bc
bb
Пример выходного файла
ab
bb
b
bc
Жюри решило поздравить авторов метода Форда-Фалкерсона, алгоритмов
Флойда-Беллмана, Кнута-Морриса-Пратта, формы Бэкуса-Науэра, схемы
Ривеста-Шамира-Адлемана и других классиков 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
Задан ориентированный ациклический граф. Требуется построить наименьшее
количество путей, покрывающих все вершины этого графа и не пересекающихся
ни по одной из вершин.
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
В некоторой стране протянута сеть железных дорог. Требуется наладить
сообщение между двумя различными городами 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]
Задача 102894 (#11)[Считай путем ] |
|
|
Входные данные
Входной файл содержит количество вершин графа 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)[Игра в города ] |
|
|
Входные данные
В первой строке входного файла записано целое число N – количество слов в списке (1 ≤ N ≤ 1000), а в последующих N строках – сами слова. Каждое из них является последовательностью не более чем из 10 строчных английских букв.
Выходные данные
Выведите в выходной файл слова в искомом порядке, либо сообщение «NO», если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.
Пример входного файла
4
b
ab
bc
bb
Пример выходного файла
ab
bb
b
bc
|
|
|
Решение |
Задача 102896 (#13)[Открытки и конверты ] |
|
|
Входные данные
В первой строке входного файла записаны числа 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)[Покрытие путями ] |
|
|
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
|
|
|
Решение |
Задача 102898 (#15)[Поможем МПС ] |
|
|
конечно, городов 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]
