Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки --> Квадратичные сортировки --> Сортировка "пузырьком"
---> 1 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 Отображать по:
#9
Ожерелье
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задано N чисел в закольцованном массиве. Разрешается менять два соседних числа, если они отличаются больше чем на 1. Необходимо упорядочить массив.

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.

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

Входные данные

Первая строка входных данных содержит  число N (2 ≤ N ≤ 50).

Во второй строке через пробел следуют N различных чисел от 1 до N — номера колечек, расположенных вдоль нити по часовой стрелке.

Выходные данные

Ваша программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк  не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается,  программа должна вывести одно число –1

Примеры
Входные данные
4
3 1 2 4
Выходные данные
4 2
4 1
0
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест