Версия для печати
Убрать все задачи
Заданы 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
Решение
Нарисуйте многоугольник и точку на его границе так,
что любая прямая, проходящая через эту точку, делит площадь этого
многоугольника пополам.
Решение
Рассматривается конечное множество M единичных квадратов на плоскости. Их стороны параллельны осям координат (разрешается, чтобы квадраты пересекались).
Известно, что для любой пары квадратов расстояние между их центрами не больше 2. Докажите, что существует единичный квадрат (не обязательно из множества M) со сторонами, параллельными осям, пересекающийся хотя бы по точке с каждым квадратом множества M.
Решение
На доске записано несколько последовательных натуральных чисел. Ровно 52% из них – чётные. Сколько чётных чисел записано на доске?
Решение
Фильтр
