Упражнения на слияние списков и реализация сортировки слиянием

В задачах A, B и C Вам понадобится функция eval.

A: Слияние списков

Даны два списка a и b упорядоченных по неубыванию. Объедините их в один упорядоченный список.

Решение оформите в виде функции merge(a: List[int], b: List[int]) -> List[int], возвращающей новый список и не модицифицирующей данные списки. Алгоритм должен иметь сложность \(O(n+m)\) (\(n\) — размер первого списка, \(m\) — размер второго списка).

Вызов функции Возвращаемое значение
merge([1, 5, 7], [2, 4, 4, 5])
[1, 2, 4, 4, 5, 5, 7]

B: Пересечение множеств

Даны два списка чисел, упорядоченных по возрастанию (каждый список состоит из различных элементов). Найдите пересечение данных множеств, то есть те числа, которые входят в оба массива. Алгоритм должен иметь сложность \(O(n+m)\).

Решение оформите в виде функции intersection(a: list, b: list) -> list, возвращающий пересечение двух данных списков. Полученный список должен быть упорядочен по возрастанию.

Вызов функции Возвращаемое значение
intersection([1, 3, 4, 7,9], [2, 3, 7, 10, 11])
[3, 7]

C: Сортировка слиянием

Сортировка слиянием (англ. merge sort) позволяет отсортировать данный массив при помощи \(O(n\log n)\) сравнений элементов.

Проще всего реализовать сортировку слиянием при помощи рекурсивной функции. Если длина данного массива равна 0 или 1, то массив уже отсортирован. Иначе необходимо разделить этот массив на две части равной (или отличающейся на 1) длины, каждую из них отсортировать рекурсивно, затем слить результат двух полученных массивов в исходный массив.

Реализуйте алгоритм сортировки слиянием. Решение оформите в виде функции merge_sort(a: list) -> list.

Вызов функции Возвращаемое значение
merge_sort([4, 1, 4, 8, 6, 6, 5])
[1, 4, 4, 5, 6, 6, 8]

Упражнения на нестандартные виды сортировок

В этих задачах не требуется использовать стандартную функцию sort — достаточно использовать какой-либо квадратичный алгоритм. Более того, стандартные сортировки могут быть просто неприменимы в этих задачах...

D: Оладьи

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

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

Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 7 3 9 1 5 переворачиванием трех оладий получится стопка 9 3 7 1 5.

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

Первая строка входных данных содержит натуральное число \(N\) (\(1 \le N \le 1000\)) — количество оладий в стопке. Далее идет \(N\) натуральных чисел, не превосходящих \(10^9\) — размеры оладий в стопке (сверху вниз).

Программа должна вывести последовательность натуральных чисел, не превосходящих \(N\), соответствующую количеству оладий, которое необходимо переворачивать для правильной сортировки стопки. Количество переворотов не должно превосходить \(10000\).

Ввод Вывод
3
1 3 2
2
3
2

E: Число из кусочков

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

Первая строка входных данных содержит количество кусочков \(N\le100\). Следующие \(N\) строк содержат последовательности цифр, записанных на кусочках, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.

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

Ввод Вывод
4
2
20
004
66
66220004

Указание. Эта задача — не про числа.

F: Кузнечики возвращаются

\(N\) кузнечиков сидят вдоль числовой прямой, в точках 1, 2, ..., \(N\). На кузнечиках написаны числа от \(1\) до \(N\). Необходимо расставить кузнечиков по порядку, чтобы каждый кузнечик оказался в точке, соответствующей его номеру.

Длина прыжка кузнечика равна 2 или 3. Одновременно в одной точке не могут находиться два кузнечика, поэтому единственно возможная операция перестановки кузнечиков заключается в том, что два кузнечика, сидящих в точках \(i\) и \(j\) одновременно прыгают и меняются местами. Это возможно сделать только в том случае, если \(|i-j|=2\) или \(|i-j|=3\).

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

В первой строке входных данных дан размер массива \(N\) (\(5\le N\le 100\)), во второй строке записана некоторая перестановка чисел от \(1\) до \(N\) через пробел — номера кузнечиков.

Программа должна вывести последовательность обменов кузнечиков. В каждой строке выводится два числа \(i\) и \(j\), означающих, что необходимо переставить переставить кузнечиков, сидящих в точках \(i\) и \(j\), при этом \(1\le i\le n\), \(1\le j\le n\), \(2\le|i-j|\le3\).

Ввод Вывод
5
3 4 1 5 2
2 4
1 3
2 5

G: Ожерелье

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

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

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

Первая строка входных данных содержит число \(N\) (\(2 \le N \le 50\)). Во второй строке через пробел следуют \(N\) различных чисел от 1 до \(N\) — номера колечек, расположенных вдоль нити по часовой стрелке.

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

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

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

Ввод Вывод
4
3 1 2 4
4 2
4 1
0

H: Ханойская сортировка

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

Программа получает на вход число дисков \(n\le 10\). Во второй строке записаны \(n\) чисел — номера дисков на первом стержне сверху вниз.

Перемещать диск можно только в том случае, если он кладется на диск большего номера. Выведите последовательность перекладываний, размещающая диски на любом стержне в порядке возрастания номеров. Формат вывода одного перекладывания: \(A\ B\ C\), где \(A\) — номер перемещаемого диска (\(1\le A\le n\)), \(B\) — номер стержня с которого снимается диск, \(C\) — номер стержня на который кладется диск.

Ввод Вывод
3
2 1 3
2 1 2
1 1 3
2 2 1
1 3 1