N. Сортировка вручную Ограничение времени 1 секунда Ограничение памяти 64 Мб Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Пришло время расставить книжки на полке. На ней стоят n n книг, однозначно пронумерованных целыми

24 октября 2025
Программирование

Условие:

N. Сортировка вручную
Ограничение времени 1 секунда
Ограничение памяти 64 Мб
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Пришло время расставить книжки на полке. На ней стоят
n
n книг, однозначно пронумерованных целыми числами от
1
1 до
n
n. Требуется расставить их в порядке возрастания номеров. Вы прекрасно знаете, что быстрая сортировка и сортировка вставками — быстрые методы сортировки, однако их непросто исполнять вручную. Они эффективны для компьютеров, а не для людей.

Поэтому вы решили сортировать книги, вставляя
i
i-ю книгу на
i
i-ю позицию. Сколько операций вам придётся выполнить для успешной сортировки?

Вот два примера операции:

1 3 4 5 2
→
→ 1 2 3 4 5, если мы вставляем 2 на свое место
1 3 4 5 2
→
→ 1 4 3 5 2, если мы вставляем 3 на свое место
Формат ввода
В первой строке входного файла содержится целое число
n
n (
1
⩽
n
⩽
20
1⩽n⩽20) — количество книг на полке.

Во второй строке записано
n
n различных целых чисел от
1
1 до
n
n — номера книг в том порядке, в котором они расставлены вначале.

Формат вывода
Выведите единственное целое число — минимальное количество операций указанного вида, которое придётся выполнить для сортировки.

Пример 1
Ввод Вывод
3
1 2 3
0
Пример 2
Ввод Вывод
3
2 1 3
1
Пример 3
Ввод Вывод
3
3 2 1
2
Пример 4
Ввод Вывод
9
7 2 9 4 6 8 5 3 1
5

Решение:

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

Шаги решения:

1. Понимание задачи: У нас есть массив из n книг, пронумерованных от 1 до n. Мы должны отсортировать их в порядке возрастания, вставляя каждую книгу на её правильное место.

2. Ввод данных: Сначала мы считываем количество книг n и сам массив с номерами книг.

3. Инициализация переменных: Создаем переменную для подсчета операций вставки, инициализируем её нулем.

4. Сортировка с подсчетом операций:
- Проходим по массиву книг.
- Для каждой книги проверяем, на каком месте она должна находиться.
- Если книга не на своем месте, мы считаем операцию вставки и перемещаем книгу на правильное место, сдвигая остальные книги.

5. Вывод результата: После завершения сортировки выводим количество операций.

Пример реализации:

Теперь давайте реализуем это в коде на Python:

- Мы читаем количество книг и их текущие номера. - Используем цикл, чтобы пройти по каждой книге. Если книга не на своем месте, мы находим её правильную позицию и меняем местами с книгой, которая там должна быть. - Каждый раз, когда мы меняем местами книги, мы увеличиваем счетчик операций. - В конце выводим общее количество операций. 1. Для входа: Вывод будет , так как книги уже отсортированы. 2. Для входа: Вывод будет , так как нужно только одна операция для вставки на своё место. 3. Для входа: Вывод будет , так как нужно две операции для сортировки. Таким образом, мы можем эффективно подсчитать количество операций, необходимых для сортировки книг.