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

   Решение

Нарисуйте многоугольник и точку на его границе так, что любая прямая, проходящая через эту точку, делит площадь этого многоугольника пополам.

   Решение

Рассматривается конечное множество M единичных квадратов на плоскости. Их стороны параллельны осям координат (разрешается, чтобы квадраты пересекались). Известно, что для любой пары квадратов расстояние между их центрами не больше 2. Докажите, что существует единичный квадрат (не обязательно из множества M) со сторонами, параллельными осям, пересекающийся хотя бы по точке с каждым квадратом множества M.

   Решение

На доске записано несколько последовательных натуральных чисел. Ровно 52% из них – чётные. Сколько чётных чисел записано на доске?

   Решение

Петя подсчитал количество всех возможных m-буквенных слов, в записи которых могут использоваться только четыре буквы T, O, W и N, причём в каждом слове букв T и O поровну. Вася подсчитал количество всех возможных 2m-буквенных слов, в записи которых могут использоваться только две буквы T и O, и в каждом слове этих букв поровну. У кого слов получилось больше? (Слово – это любая последовательность букв.)

   Решение

На сторонах угла взяты точки A, B. Через середину M отрезка AB проведены две прямые, одна из которых пересекает стороны угла в точках A₁, B₁, другая – в точках A₂ , B₂. Прямые A₁B₂ и A₂B₁ пересекают AB в точках P и Q. Докажите, что M – середина PQ.

   Решение

Темы:    [ Системы точек и отрезков (прочее) ] [ Теоремы Чевы и Менелая ] [ Центральная симметрия помогает решить задачу ] [ Применение проективных преобразований прямой в задачах на доказательство ]

Сложность: 4 Классы: 8,9,10,11

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

Условие

На сторонах угла взяты точки A, B. Через середину M отрезка AB проведены две прямые, одна из которых пересекает стороны угла в точках A₁, B₁, другая – в точках A₂ , B₂. Прямые A₁B₂ и A₂B₁ пересекают AB в точках P и Q. Докажите, что M – середина PQ.

Решение 1

  Пусть C – вершина данного угла (см. рис.). Применив теорему Менелая (см. задачу 53857) к треугольнику ABC и прямой A₂B₂, получим
  Аналогично,  
  Применив теорему Менелая к треугольнику ABC и прямой A₁B₂, получим     откуда  
  Аналогично     Следовательно, PA = QB, что и требовалось.

Решение 2

  Сделаем центральную симметрию относительно точки M. Пусть точки A₁ и B₂ переходят в точки A₃ и B₃ соответственно. Надо доказать, что прямые AB, A₂B₁ и B₃A₃ пересекаются в одной точке. Далее можно рассуждать по-разному.

  Первый способ. Проведём через точку M прямую, параллельную BC. Из подобия треугольников следует, что

  где X – точка пересечения прямых AB и B₁B₃. Перемножив, получаем

  Из теоремы Чевы (см. задачу 53856), примененной к треугольнику MB₁B₂, следует, что прямые MX, B₁A₂ и B₃A₃ пересекаются в одной точке, что и требовалось.

  Второй способ. Прямые AA₂ и BB₁, пересекаются в точке C; прямые A₂B₃ и B₁A₃, совпадающие соответственно с A₂B₂ и B1A₁, пересекаются в точке M. Прямые AB₃ и BA, симметричные соответственно BB₂ и AA₁, пересекаются в точке C₁, симметричной точке C. Точки C, M и C₁ лежат на одной прямой, поэтому из теоремы, обратной к теореме Дезарга, применённой к треугольникам AA₂B₃ и BB₁A₃, следует, что прямые AB, A₂B₁ и B₃A₃ пересекаются в одной точке.

Решение 3

  Рассматривая центральные проекции прямой AB на прямую AC из точек B₁, B₂, получаем равенство двойных отношений (см. рис.)
(APMB) = (AA₁A₂C) = (CA₂A₁A) = (BQMA),  что равносильно утверждению задачи.

Источники и прецеденты использования