Версия для печати
Убрать все задачи

---

Имя входного файла:	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

   Решение

Темы:    [ Пирамида (прочее) ] [ Признаки перпендикулярности ] [ Прямоугольные треугольники (прочее) ]

Сложность: 3+ Классы: 10,11

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

Условие

Каждая боковая грань пирамиды является прямоугольным треугольником, в котором прямой угол примыкает к основанию пирамиды. В пирамиде проведена высота. Может ли она лежать внутри пирамиды?

Решение

  Пусть основанием пирамиды SA₁...A_n является многоугольник A₁...A_n (см. рисунки). Возможны два случая.
  1) Соседние углы в двух соседних боковых гранях – прямые. Пусть, например,  ∠SA₂A₁ = ∠SA₂A₃ = 90°  (рис. слева). Тогда по признаку перпендикулярности прямой и плоскости  SA₂ ⊥ A₁A₂A₃,  то есть SA₂ – высота пирамиды, и она принадлежит боковой поверхности пирамиды.

  2) В любых двух соседних боковых гранях прямые углы не имеют общей вершины. Пусть в прямоугольных треугольниках SA_nA₁, SA₁A₂, ..., SA_n–1A_n вершинами прямых углов являются точки A₁, A₂, ..., A_n соответственно (рис. справа). Воспользуемся тем, что гипотенуза больше катета. Тогда из треугольника SA₁A₂  SA₁ > SA₂,  из треугольника SA₂A₃  SA₂ > SA₃,  и так далее.
  Записав аналогичные неравенства для каждой боковой грани, получим  SA₁ > SA₂ > ... > SA_n > SA₁,  то есть  SA₁ > SA₁.  Противоречие.
  Таким образом, внутри данной пирамиды высота лежать не может.

Ответ

Не может.

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