Задан ориентированный граф с 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

   Решение

Страница: << 23 24 25 26 27 28 29 >> [Всего задач: 277]      

Задано уравнение вида A + B = C, где A, B и C – неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно.

Входные данные
Заданное уравнение содержится в первой строке входного файла. Длина уравнения не превышает 80 символов. Входной файл не содержит пробелов.

Выходные данные
В выходной файл требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение «решения не существует».

Пример входного файла
??2?4+9?=355

Пример выходного файла
00264+91=355

Прислать комментарий

Решение

Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:
    a) определяет, является ли заданный граф четно-нечетным;
    б) В случае отрицательного ответа на пункт а) находит максимальное подмножество X вершин графа такое, что для любых двух вершин i и j из X выполняется следующее условие: все пути между i и j состоят из четного числа ребер.

Входные данные
Первая строка входного файла содержит число вершин графа N (1 ≤ N ≤ 100), а каждая последующая – пару чисел (i, j), означающих, что в графе присутствует ребро, соединяющее вершины с номерами i и j.

Выходные данные
Первая строка выходного файла должна содержать ответ на пункт А в форме YES/NO. В случае отрицательного ответа на пункт А вторая строка должна содержать количество вершин в множестве X, а третья – номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них.

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

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

Прислать комментарий

Решение

В стране N городов, в каждом из которых есть аэропорт. Авиакомпания, занимающаяся перевозкой грузов, имеет самолет и желает максимально выгодно его использовать. Для некоторых пар городов (A, B) известны время перелета из A в B и сумма выручки за доставку груза из A в B. Напишите программу, которая по этим данным находит для самолета замкнутый путь, максимизирующий среднюю выручку за единицу времени.

Считается, что самолет может вместить не более одного груза, а временем стоянки самолета в аэропорту следует пренебречь.

Входные данные
В первой строке входного файла содержится число городов N (1 ≤ N ≤ 100) и число возможных прямых рейсов M. В каждой из следующих M строк записана четверка чисел (i, j, b_ij, c_ij), описывающая возможный рейс между городами i и j со временем перелета b_ij и выручкой c_ij . Время перелета и выручка – положительные вещественные числа.

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

Пример входного файла
3 3
1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0

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

Прислать комментарий

Решение

Задан ориентированный граф с 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

Прислать комментарий

Решение

Страница: << 23 24 25 26 27 28 29 >> [Всего задач: 277]