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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .

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

	Странная сортировка 23.02.2023, 15:12. Показов 3202. Ответов 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

Опции темы