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

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

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

На проверку сдайте только тело функции.

merge([1, 5, 7], [2, 4, 4, 5])

[1, 2, 4, 4, 5, 5, 7]

a = eval(input())
a_copy = a[:]
b = eval(input())
b_copy = b[:]
res = merge(a, b)
if a != a_copy or b != b_copy:
    print("Фунция не должна модифицировать передаваемые параметры")
if type(res) != list:
    print("Функция должна возвращать список")
else:
    print(res)

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

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

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

На проверку сдайте только тело функции.

intersection([1, 3, 4, 7, 9], [2, 3, 7, 10, 11])

[3, 7]

a = eval(input())
a_copy = a[:]
b = eval(input())
b_copy = b[:]
res = intersection(a, b)
if a != a_copy or b != b_copy:
    print("Фунция не должна модифицировать передаваемые параметры")
if type(res) != list:
    print("Функция должна возвращать список")
else:
    print(res)

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]

a = eval(input())
a_copy = a[:]
res = merge_sort(a)
if a != a_copy:
    print("Фунция не должна модифицировать передаваемые параметры")
if type(res) != list:
    print("Функция должна возвращать список")
else:
    print(res)

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: Упорядочить список из 4 элементов за 5 сравнений

Напишите функцию def sort4(a: list), упорядочивающую данный список a по неубыванию элементов. Предполагается, что в списке не более 4 элементов. Функция должна вне зависимости от входных данных выполнять не более 5 сравнений элементов между собой при помощи операций “меньше” или “больше”.

Функция не возвращает значение, а переставляет элементы переданного списка.

Пример реализации аналогичной функции для 3 элементов:

def sort3(a):
    if a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
    if a[1] > a[2]:
        a[1], a[2] = a[2], a[1]
    if a[0] > a[1]:
        a[0], a[1] = a[1], a[0]

Сдайте на проверку только тело функции.

class Int:
    num_cmp = 0
    def __init__(self, s=0):
        self.__data = int(s)
    def __lt__(self, other):
        Int.num_cmp += 1
        return self.__data < other.__data
    def __eq__(self, other):
        return self.__data == other.__data
    def __str__(self):
        return str(self.__data)
    def __repr__(self):
        return str(self.__data)
src = [Int(i) for i in range(1, 5)]
for perm in itertools.permutations(src):
    perm = list(perm)
    Int.num_cmp = 0
    perm_sorted = perm[:]
    sort4(perm_sorted)
    if perm_sorted != src:
        print("Сортировка работает неправильно")
        print("Исходный список:", perm)
        print("Список после сортировки:", perm_sorted)
        break
    if Int.num_cmp > 5:
        print("Выполнено слишком много сравнений:", Int.num_cmp)
        print("Исходный список:", perm)
        break
else:
    print("OK")

I: Упорядочить список из 5 элементов за 7 сравнений

Напишите фунцию сортировки списка из 5 элементов, на любом входе производящую не более 7 сравнений. Решение оформите в виде функции def sort5(a: list).

Сдайте на проверку только тело функции.

Эту задачу вряд ли получиться решить без использования вложенных условных инструкций.

class Int:
    num_cmp = 0
    def __init__(self, s=0):
        self.__data = int(s)
    def __lt__(self, other):
        Int.num_cmp += 1
        return self.__data < other.__data
    def __eq__(self, other):
        return self.__data == other.__data
    def __str__(self):
        return str(self.__data)
    def __repr__(self):
        return str(self.__data)
src = [Int(i) for i in range(1, 6)]
for perm in itertools.permutations(src):
    perm = list(perm)
    Int.num_cmp = 0
    perm_sorted = perm[:]
    sort5(perm_sorted)
    if perm_sorted != src:
        print("Сортировка работает неправильно")
        print("Исходный список:", perm)
        print("Список после сортировки:", perm_sorted)
        break
    if Int.num_cmp > 7:
        print("Выполнено слишком много сравнений:", Int.num_cmp)
        print("Исходный список:", perm)
        break
else:
    print("OK")

J: Количество инверсий

Для заданного списка чисел найдите количество таких пар \((i, j)\), что \(i\lt j\) и \(a_i \gt a_j\).

Первая строка содержит число \(n\) — количество элементов в списке. Вторая строка содержит \(n\) различных целых чисел.

Программа должна вывести одно число — количество инверсий в данном списке. Решение должно иметь сложность \(O(n\log(n))\).

Указание: используйте сортировку слиянием.

5
6 11 18 28 31

0

8
94 89 82 72 69 61 54 50

28

K: Таблица инверсий

Для каждого элемента заданного массива из \(n\) чисел определите, сколько в данном массиве элементов, которые идут раньше него и при этом больше него.

Программа должна вывести \(n\) чисел — ответ для каждого элемента массива. Решение должно иметь сложность \(O(n\log(n))\).

6
4 8 2 5 4 3

0 0 2 1 2 4