Фильтр
Выбрана 1 задача Убрать все задачи
Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v1 и v2 и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v1 в v2 .
Входные данные
Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов.
Наконец, строка N+2 содержит номера вершин v1
и v2
, а строка N+3 – десятичную запись числа C (1 &le C <
1050).
Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи:
«Yes», если путь длины C существует, и «No», если нет. Во вторую строку
запишите ответ на второй пункт задачи. Если ни одного пути из v1
в v2
не существует, ваша программа должна вывести -1.
Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555
Пример выходного файла
Yes
0
Решение
Задачи
Задача 32028 (#01) |
|
|
Все натуральные числа поделены на хорошие и плохие. Известно, что если число m хорошее, то и число m + 6 тоже хорошее, а если число n плохое, то и число n + 15 тоже плохое. Может ли среди первых 2000 чисел быть ровно 1000 хороших?
|
|
Решение |
Задача 32029 (#02) |
|
|
Какое наибольшее число пешек можно поставить на шахматную доску (не более одной пешки на каждое поле), если:
1) на поле e4 пешку ставить нельзя;
2) никакие две пешки не могут стоять на полях, симметричных относительно поля e4?
|
|
|
Решение |
Задача 32030 (#03) |
|
|
Сколько двоек будет в разложении на простые множители числа 1984! ?
|
|
|
Решение |
Задача 32031 (#04) |
|
|
В ряд выписаны в порядке возрастания числа, делящиеся на 9: 9, 18, 27, 36, ... . Под каждым числом этого ряда записана его сумма цифр.
а) На каком месте во втором ряду впервые встретится число 81?
б) Что встретится раньше: четыре раза подряд число 27 или один раз число 36?
|
|
|
Решение |
Задача 32032 (#05) |
|
|
На плоскости имеется 1983 точки и окружность единичного радиуса.
Доказать, что на окружности найдётся точка, сумма расстояний от которой до данных точек не меньше 1983.
|
|
|
Решение |
Страница: 1 2 >> [Всего задач: 7]
