Странная сортировка

@Valentin000000 · Регистрация: 05.04.2022

Студворк — интернет-сервис помощи студентам

ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт

Дан массив из чисел от 1 до n, каждое число встречается в массиве ровно один раз. За одно действие вы можете менять местами два элемента этого массива, если они стоят через один или через два (то есть, можно поменять элементы с индексами x и x+2, или элементы с индексами x и x+3). Ваша задача — отсортировать массив, совершив не более 2000 операций.

Входные данные
Первая строка содержит число n (2≤n≤100). Вторая строка содержит n чисел от 1 до n — элементы массива.

Выходные данные
В первой строке выведите число действий k (k≤2000). В следующих k строках выведите пары чисел x,y — индексы элементов, которые нужно поменять местами (1≤x<y≤n, y=x+2 или y=x+3).

Если решений несколько, выведите любое. Если решения нет, выведите одно число −1.

@TheCalligrapher · 24.02.2023, 20:33

Сообщение от Pythonistj

Помогиет

Не понял. А почему вопрос был от Valentin000000, а чебуреки сулит некто Pythonistj?

Verevkin · 24.02.2023, 20:38

Сообщение от TheCalligrapher

Не понял. А почему вопрос был от Valentin000000, а чебуреки сулит некто Pythonistj?

А вот поэтому.

@TheCalligrapher · 24.02.2023, 20:40

Сообщение от Verevkin

А вот поэтому.

По всей стране началось?

Verevkin · 24.02.2023, 20:42

Сообщение от TheCalligrapher

По всей стране началось?

По всем интырнетам!

Глянь это.

@TheCalligrapher · 25.02.2023, 10:35

Сообщение от TheCalligrapher

Мой вариант: 50 обменов
Вариант Verevkin: 52 обмена

Кстати, насколько я вижу, делаем мы одно и то же.

Однако при необходимости выполнить обмен двух далеких элементов массива я "раскладываю" этот обмен в сумму обменов "сначала по 2, потом по 3" (если смотреть справа-налево), а Verevkin раскладывает в "сначала по 3, потом по 2". То есть разница как будто совершенно не принципиальная, но в моем варианте промежуточные элементы, случайно затронутые такими далекими перестановками, почему-то укладываются более удачно и в итоге получается чуть меньше перестановок. Случайность?

Алексей1153 · 25.02.2023, 11:24

Сообщение от Pythonistj

20 СЕК СОС ХЭЛП ВВОД НАПИШИТЕ Т
Добавлено через 18 секунд
Помогиет

ми иво тиряем (

Добавлено через 30 секунд
долго возились, господа, ай ай ай

Verevkin · 25.02.2023, 11:28

Сообщение от TheCalligrapher

Случайность?

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@Valentin000000 0 / 0 / 0 Регистрация: 05.04.2022 Сообщений: 20

	Странная сортировка 23.02.2023, 15:12. Показов 3184. Ответов 26 Метки задача, с++ (Все метки) ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт Дан массив из чисел от 1 до n, каждое число встречается в массиве ровно один раз. За одно действие вы можете менять местами два элемента этого массива, если они стоят через один или через два (то есть, можно поменять элементы с индексами x и x+2, или элементы с индексами x и x+3). Ваша задача — отсортировать массив, совершив не более 2000 операций. Входные данные Первая строка содержит число n (2≤n≤100). Вторая строка содержит n чисел от 1 до n — элементы массива. Выходные данные В первой строке выведите число действий k (k≤2000). В следующих k строках выведите пары чисел x,y — индексы элементов, которые нужно поменять местами (1≤x<y≤n, y=x+2 или y=x+3). Если решений несколько, выведите любое. Если решения нет, выведите одно число −1. 0