Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Замкнутая сортировка

(Время: 1 сек. Память: 16 Мб Сложность: 36%)

Задан целочисленный массив A[1..N] из N различных чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N. Будем считать, что первый и последний элементы массива соединены таким образом, что за последним следует первый, а перед первым располагается последний. Мы получили замкнутую последовательность чисел без начала и конца.

Требуется отсортировать такой массив (упорядочить в нем элементы по возрастанию), при этом следует соблюдать следующие ограничения:

  1. Разрешается менять местами только два соседних элемента массива.
  2. Не разрешается менять местами элементы, если они отличаются ровно на единицу.

Например, если исходный массив из шести элементов имеет вид [2, 1, 3, 6, 4, 5], то мы должны получить в результате, например, такой массив: [4, 5, 6, 1, 2, 3]. В результате, правее каждого элемента должен стоять превосходящий его ровно на единицу, кроме N (справа от N должна быть единица).

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

Первая строка входного файла INPUT.TXT содержит целое число N – размер входного массива (2 ≤ N ≤ 50). Вторая строка содержит N целых чисел – исходную перестановку чисел от 1 до N в массиве.

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

В выходной файл OUTPUT.TXT выведите K строк, где K – количество обменов в сортировке. На каждой строке выведите по два числа xi и yi, разделенных пробелом – значения меняемых элементов массива на i-м шаге. В последней строке выходных данных должен стоять 0. Помните, что должно выполняться условие |xi–yi| > 1 и что менять можно только соседние элементы массива. Если существует несколько решений, то разрешается вывести любое из них. Количество строк выходного файла не должно превышать 50 000. Если же такого решения не существует, то следует вывести «impossible» (без кавычек).

Пример

INPUT.TXTOUTPUT.TXTПояснение
14
3 2 4 1
1 3
2 4
1 4
0
1 2 4 3
1 4 2 3
4 1 2 3

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023 7-8 классы
 2022 / 2023 9-11 классы
 2023 / 2024 7-8 классы
 2023 / 2024 9-11 классы
 A. Температура
 B. Cashback
 C. Путешествие вдоль реки
 D. Автобус №13
 E. Замкнутая сортировка

Красноярский краевой Дворец пионеров, (c)2006 - 2023, ИНН 246305493507, E-mail: admin@acmp.ru