Дано n чисел, x₁, x₂, ..., x_n, при этом  x_k = ±1.  Доказать, что если  x₁x₂ + x₂x₃ + ... + x_nx₁ = 0,  то n делится на 4.

   Решение

Заданы 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

   Решение

Докажите, что в любой выпуклый многоугольник площади 1 можно поместить треугольник, площадь которого не меньше: а) 1/4; б) 3/8.

   Решение

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

Докажите, что площадь треугольника, вершины которого лежат на сторонах параллелограмма, не превосходит половины площади параллелограмма.

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

Решение

Докажите, что любой остроугольный треугольник площади 1 можно поместить в прямоугольный треугольник площади .

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

Решение

а) Докажите, что выпуклый многоугольник площади S можно поместить в некоторый прямоугольник площади не более 2S.
б) Докажите, что в выпуклый многоугольник площади S можно вписать параллелограмм площади не менее S/2.

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

Решение

Докажите, что в любой выпуклый многоугольник площади 1 можно поместить треугольник, площадь которого не меньше: а) 1/4; б) 3/8.

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

Решение

Выпуклый n-угольник помещен в квадрат со стороной 1. Докажите, что найдутся три такие вершины A, B и C этого n-угольника, что площадь треугольника ABC не превосходит: а) 8/n²; б) 16/n³.

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

Решение

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