Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v₁ и v₂ и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v₁ в вершину v₂, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v₁ в v₂ .

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

Наконец, строка N+2 содержит номера вершин v₁ и v₂ , а строка N+3 – десятичную запись числа C (1 &le C < 10⁵⁰).

Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v₁ в v₂ не существует, ваша программа должна вывести -1.

Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555

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

   Решение

Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 96]      

Точка M делит среднюю линию треугольника ABC, параллельную стороне BC, на отрезки, один из которых в три раза длиннее другого. Точка N делит сторону BC на отрезки, один из которых в три раза длиннее другого. В каком отношении прямая MN делит площадь треугольника ABC?

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

Решение

На продолжении стороны AB за точку B треугольника ABC отложен отрезок AD, причём AD : AB = . На продолжении медианы BE отложен отрезок EF, причём EF : BE = . Найдите отношение площадей треугольников BDF и ABC.

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

Решение

Дан треугольник ABC, площадь которого равна 2. На медианах AK, BL и CN треугольника ABC взяты соответственно точки P, Q и R так, что AP : PK = 1, BQ : QL = 1 : 2, CR : RN = 5 : 4. Найдите площадь треугольника PQR.

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

Решение

На сторонах выпуклого четырёхугольника ABCD, площадь которого равна 2, взяты точки: K на AB, L на BC, M на CD, N на AD. При этом AK : KB = 2, BL : LC = 1 : 3, CM : MD = 1, DN : NA = 1 : 5. Найдите площадь шестиугольника AKLCMN.

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

Решение

В треугольнике со сторонами a, b и c проведены биссектрисы, точки пересечения которых с противолежащими сторонами являются вершинами второго треугольника. Докажите, что отношение площадей этих треугольников равно .

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

Решение

Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 96]