Выбрано 2 задачи 
Убрать все задачи
|
Имя входного файла: |
necklace.in |
|
Имя выходного файла: |
necklace.out |
|
Максимальное время работы на одном тесте: |
1 секунда |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.
Формат входных данных
В первой строке входного файла записано число N (2 ≤ N ≤ 50).
Во второй строке через пробел следуют N различных чисел от 1 до N - номера колечек, расположенных вдоль нити по часовой стрелке.
Формат выходных данных
Выходной файл должен содержать описание процесса упорядочения.
В каждой строке, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.
Количество строк выходного файла не должно превышать 50000.
Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число √1.
Пример
|
necklace.in |
necklace.out |
|
4 3 2 4 1 |
1 3 2 4 1 4 0 |
РешениеНайдите корень уравнения 81x-8 =
Решение |
|
 |
Условие
Пусть O, I – центры описанной и вписанной окружностей прямоугольного треугольника; R, r – радиусы этих окружностей; J – точка, симметричная вершине прямого угла относительно I. Найдите OJ.
Решение 1
Пусть ABC – данный прямоугольный треугольник, ∠C = 90°. Очевидно, что окружность с центром J и радиусом 2r касается AC и BC. Докажем, что она касается также описанной окружности Ω треугольника ABC; отсюда как раз и будет следовать, что OJ = R – 2r.
Рассмотрим окружность ω, касающуюся AC, BC в точках P, Q соответственно, и касающуюся Ω изнутри в точке T; нам надо доказать, что J – центр ω. Так как T – центр гомотетии ω и Ω, прямые TP, TQ вторично пересекают описанную окружность в точках, касательные в которых параллельны AC и BC, то есть в серединах B', A' дуг AC, C. Поэтому прямые AA' и BB' пересекаются в точке I. По теореме Паскаля (см. задачу 57105), применённой к ломаной CAA'TB'B, точки P, I, Q лежат на одной прямой. Поскольку прямая PQ перпендикулярна биссектрисе угла C, P, Q – проекции J на AC и BC, что и означает, что J – центр ω.
Решение 2
По формуле Эйлера (см. задачу 52464) OI² = R(R – 2r). Поскольку OI – медиана треугольника OCJ, 4OI² = 2(OC² + OJ²) – CJ², или
4R(R – 2r) = 2R² + 2OJ² – 8r², откуда и следует, что OJ² = (R – 2r)².
Ответ
R – 2r.
