Выбрано 15 задач 
Убрать все задачи
Заданы 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% из них – чётные. Сколько чётных чисел записано на доске?
Петя подсчитал количество всех возможных m-буквенных слов, в записи которых могут использоваться только четыре буквы T, O, W и N, причём в каждом слове букв T и O поровну. Вася подсчитал количество всех возможных 2m-буквенных слов, в записи которых могут использоваться только две буквы T и O, и в каждом слове этих букв поровну. У кого слов получилось больше? (Слово – это любая последовательность букв.)
На сторонах угла взяты точки A, B. Через середину M отрезка AB проведены две прямые, одна из которых пересекает стороны угла в точках A1, B1, другая – в точках A2 , B2. Прямые A1B2 и A2B1 пересекают AB в точках P и Q. Докажите, что M – середина PQ.
Вписанная окружность треугольника ABC касается сторон BC, CA, ABв точках A', B', C' соответственно. Прямые AA', BB' и CC' пересекаются в точке G. Описанная окружность треугольника GA'B', вторично пересекает прямые AC и BC в точках CA и CB. Аналогично определяются точки AB, AC, BC, BA. Докажите, что точки AB, AC, BC, BA, CA, CB лежат на одной окружности.
Дано:
Докажите, что
В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику.
Докажите, что площадь проекции куба с ребром 1 на любую плоскость численно равна длине его проекции на прямую, перпендикулярную этой плоскости.
Точка A лежит в плоскости α , ортогональная проекция отрезка AB на эту плоскость равна 1, AB = 2 . Найдите расстояние от точки B до плоскости α .
Среди всех треугольников, вписанных в данную окружность, найдите тот,
у которого максимальна сумма квадратов длин сторон.
Каждая деталь конструктора "Юный паяльщик" – это скобка в виде буквы П, состоящая из трёх единичных отрезков. Можно ли из деталей этого конструктора спаять полный проволочный каркас куба 2×2×2, разбитого на кубики 1×1×1? (Каркас состоит из 27 точек, соединённых единичными отрезками; любые две соседние точки должны быть соединены ровно одним проволочным отрезком.)
Около сферы радиуса 10 описан некоторый 19-гранник. Доказать, что на его поверхности найдутся две точки, расстояние между которыми больше 21.
B треугольнике ABC угол A равен 120°. Докажите, что расстояние от центра описанной окружности до ортоцентра равно AB + AC.
|
|
 |
Условие
B треугольнике ABC угол A равен 120°. Докажите, что расстояние от центра описанной окружности до ортоцентра равно AB + AC.
Решение 1
Пусть C1 и B1 – основания высот треугольника ABC, проведённых к сторонам AB и AC соответственно, H – ортоцентр, O – центр описанной окружности, D – середина большей из дуг BC этой окружности. Tогда треугольник BDC – равносторонний, и по задаче 52355, AD = AB + AC.
Прямые OD и AH параллельны как перпендикуляры
к BC. Kроме того, согласно задаче 55599 AH = OD. Значит, ODAH – параллелограмм, и
OH = AD = AB + AC.
Решение 2
Hа продолжении стороны AC за точку A отложим отрезок AB' = AB. Докажем, что OH = СB'. Для этого достаточно показать, что OB'HC – равнобокая трапеция (или прямоугольник). Треугольник AB'B – равносторонний, поэтому OB' ⊥ AB. Следовательно, OB' || HC.
Tак как BB1 – высота равностороннего треугольника AB'B, то BB1, а следовательно, и HB – серединный перпендикуляр к отрезку AB', то есть HB' = HA. Пусть K – середина отрезка BC, тогда HA = 2OK (расстояние от ортоцентра треугольника до вершины в два раза больше расстояния от центра описанной окружности до противолежащей этой вершине стороны). Поскольку ∠BOC = 120°, то ∠KCO = 30°, то есть KCO – прямоугольный треугольник с углом 30°. Следовательно, OC = 2OK, откуда OC = HB'.
