Хитрые сортировки в Python

Иногда возникает необходимость сортировать не только числовые последовательности, но и более сложные объекты, а также сохранять при сортировке знание о позиции элемента в исходной последовательности. Всё это в языки Python делается довольно просто и элегантно.

Начнём с того, что Python умеет сравнивать списки:

>>> [1, 2, 3, 4] > [2, 3, 4]
False
>>> [1, 2, 3, 4] > [1, 2, 3, 4]
False
>>> [1, 3, 2, 4] > [1, 2, 3, 4]
True
>>> [1, 2, 3, 4, 5] > [1, 2, 3, 4]
True
>>> [10] > [1, 2, 3, 4]
True
>>> [2, -100] > [1, 2, 3, 4]
True
Сравнивает он их поэлементно (или лексикографически), то есть сначала сравнивает первые элементы. Владелец большего первого элемента и сам больше. Если же первые элементы совпадают, то мы сравниваем вторые элементы. Так мы движемся до тех пор, пока i-й элемент одного списка не станет больше i-го элемента второго списка, тогда первый победит. Если какой-то список закончился раньше, то он меньше. А иначе списки совпадают.

Итак, если списки можно сравнивать, то их можно и сортировать.

>>> A = [[1, 2, 3, 4], [2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4, 5], [10], [2, -100], [1, 3, 2, 4], [1, 2, 3, 4]]
>>> sorted(A)
[[1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4],
 [1, 2, 3, 4, 5],
 [1, 3, 2, 4],
 [2, -100],
 [2, 3, 4],
 [10]]

Конечно же, для того, чтобы такой «сложный» список можно было отсортировать, необходимо, чтобы его элементы можно было сравнить.

>>> sorted([[1, 2], [1, 'a']])
Traceback (most recent call last):
  File "< string >", line 301, in runcode
  File "< interactive input >", line 1, in < module >
TypeError: unorderable types: str() < int()

Теперь представим себе, что нам нужно отсторировать список, но при этом нужно сохнанить знание о том, где стоял элемент до сортировки. Для этого можно применить такой трюк: заменим число x на кортеж (x, i), где i — номер элемента в списке. И после этого отсортируем.

my_list = [39, 12, 21, 77, 21, 51, 48, 21, 42, 76]
for i in range(len(my_list)):
    my_list[i] = (my_list[i], i)
my_list.sort()
print(my_list)

[(12, 1), (21, 2), (21, 4), (21, 7), (39, 0), (42, 8), (48, 6), (51, 5), (76, 9), (77, 3)]

Благодаря такой операции мы знаем, что числа 21 стояли на 2, 4 и 7-й позиции в исходном списке, а наибольшее число 77 было на позиции 3. Всё это можно сделать короче с помощью генератора списков:

my_list = [39, 12, 21, 77, 21, 51, 48, 21, 42, 76]
hacked_list = sorted([(my_list[i], i) for i in range(len(my_list))])

Параметр key у метода sort и функции sorted

Допустим, у нас есть список названий деталей и их стоимостей. Нам нужно отсторитровать его сначала по названию деталей, а одинаковые детали по убыванию цены. Самая коротка реализация даст не совсем тот результат:
shop = [['каретка', 1200], ['шатун', 1000], ['седло', 300], ['педаль', 100], ['седло', 1500], ['рама', 12000], ['обод', 2000], ['шатун', 200], ['седло', 2700]]
shop.sort()
for i in range(len(shop)):
    print('{:<10} цена: {:>5}р.'.format(shop[i][0], shop[i][1]))
каретка    цена:  1200р.
обод       цена:  2000р.
педаль     цена:   100р.
рама       цена: 12000р.
седло      цена:   300р.
седло      цена:  1500р.
седло      цена:  2700р.
шатун      цена:   200р.
шатун      цена:  1000р.
Как и следовало ожидать, одинаковые детали отсортированы по возрастанию цены (не обращайте пока внимания на format, или почитайте документацию).

Это можно исправить так:

def prepare_item(item):
    return (item[0], -item[1])

shop = [['каретка', 1200], ['шатун', 1000], ['седло', 300], ['педаль', 100], ['седло', 1500], ['рама', 12000], ['обод', 2000], ['шатун', 200], ['седло', 2700]]
shop.sort(key=prepare_item)
for i in range(len(shop)):
    print('{:<10} цена: {:>5}р.'.format(shop[i][0], shop[i][1]))
каретка    цена:  1200р.
обод       цена:  2000р.
педаль     цена:   100р.
рама       цена: 12000р.
седло      цена:  2700р.
седло      цена:  1500р.
седло      цена:   300р.
шатун      цена:  1000р.
шатун      цена:   200р.
Что здесь произошло? Перед тем, как сравнивать два элемента списка к ним применялась функция prepare_item, которая меняла знак у стоимости. В результате при одинаковов первом значении сортировка по второму происходила в обратном порядке.

Ещё можно писать так (но делать это нужно аккуратно и с пониманием):

shop.sort(key=lambda x: (x[0], -x[1]))

Используя подходящую функцию prepare_item мы можем делать и более сложные сортировки:
Отсортировать только по второму элементу

def prepare_item(item):
    return item[1]
Отсортировать по модулю третьего элемента:
def prepare_item(item):
    return abs(item[2])
Отсортировать сначала по третьему элементу списка, затем по модулю первого:
def prepare_item(item):
    return (item[2], abs(item[0]))

Другой способ хитрых сортировок

Допустим данные нужно отсортировать сначала по столбцу А по возрастанию, затем по столбцу Б по убыванию, и наконец по столбцу В снова по возрастанию. Если данные в столбце Б числовые, то при помощи подходящей функции в key можно поменять знак у элементов Б, что приведёт к необходимому результату. А если все данные текстовые? Тут есть такая возможность. Дело в том, что сортировка sort в Python устойчивая, то есть она не меняет порядок «одинаковых» элементов. Поэтому можно просто отсортировать три раза по разным ключам:

data.sort(key=lambda x: x['В'])
data.sort(key=lambda x: x['Б'], reverse=True)
data.sort(key=lambda x: x['А'])

Упражнения

A: Четвертная оценка

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

При этом если у школьника есть двойка, а следующая за ней оценка – не двойка, то двойка считается закрытой, и при вычислении среднего арифметического не учитывается.

Вводится десять натуральных чисел от 2 до 5 через пробел – оценки Васи.

Выведите натуральное число (от 2 до 5) – его четвертную оценку.

2 5 2 5 2 5 2 5 2 5
5
2 2 2 2 2 2 2 2 2 5
2
5 5 5 5 5 5 5 5 5 2
4

B: Пассажиры метро

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

Программа получает на вход число пассажиров \(N\). Далее в \(N\) строчках записано время входа \(A_i\) и время выхода \(B_i\) каждого пассажира (\(A_i\lt B_i\)). Время задается в минутах от начала работы метрополитена.

В следующей строке дано время \(T\). Выведите одно число: количество пассажиров в момент времени \(T\). Если какой-то пассажир в момент \(T\) входит или выходит, то его тоже необходимо посчитать.

4 3 12 8 9 5 10 10 12 10
3

C: Навстречу

Дана последовательность чисел. Вывести ее в след. порядке: первое число, последнее, второе, предпоследнее и так далее все числа (см. пример).

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

Выведите числа в требуемом порядке через пробел.

5 1 2 3 4 5
1 5 2 4 3
4 1 2 3 4
1 4 2 3

D: Час пик

Не без вашей помощи в метро посчитали количество пассажиров в каждый час работы метро. Теперь вас просят по этим данным найти «час пик» такие \(k\) подряд идущих часов, что суммарное число пассажиров в эти часы максимальное.

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

Найдите \(K\) подряд идущих часов работы метрополитена с максимальным суммарным числом пассажиров и выведите суммарное число пассажиров за эти часы.

7 3 2 5 4 3 2 4 3
12

E: Треугольник Паскаля

По данному числу \(N\) выведите первые \(N + 1\) строку треугольника Паскаля. Числа в строке разделяйте одним пробелом.

4
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

Указание. Стройте строки треугольника Паскаля последовательно. Заведите два списка: для хранения последней построенной строки треугольника Паскаля и следующей за ней.

F: Два совпадающих элемента

В массиве ровно два элемента равны. Найдите эти элементы.

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

Выведите значение совпадающих элементов.

6 8 3 5 4 5 1
5

G: Двойной переворот

Дана последовательность натуральных чисел 1, 2, 3, ..., \(N\) (\(1 \le N \le 1000\)). Необходимо сначала расположить в обратном порядке часть этой последовательности от элемента с номером \(A\) до элемента с номером \(B\), а затем от \(C\) до \(D\) (\(A \le B\); \(C \le D\); \(1 \le A, B, C, D \le N\)).

Даны числа \(N\), \(A\), \(B\), \(C\), \(D\).

Требуется вывести полученную последовательность.

9 2 5 6 9
1 5 4 3 2 9 8 7 6
9 3 6 5 8
1 2 6 5 8 7 3 4 9

H: Диаметр множества

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

Первая строка входных данных содержит число точек \(N\). Далее в \(N\) строках записано по два целых числа \(x_i\) и \(y_i\) — координаты точек.

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

3 1 1 1 0 0 0
1.4142135623731

I: Автомат со сдачей

Одна фирма обслуживает автоматы по продаже чая и кофе.

Стоимость стакана чая и кофе в автомате равна пяти рублям. Автомат принимает монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда покупателю надо выдавать сдачу (т.е. когда покупатель бросил в автомат десятирублёвую монету или 10-, 50- или 100-рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же покупатель бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим покупателям.

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

В первой строке входных данных находится одно натуральное число \(N\) — количество покупок в автомате, которые были совершены в ходе испытания (\(1\leq N\leq 50\,000\)). Во второй строке находятся \(N\) натуральных чисел, каждое из которых равно номиналу монеты или купюры, которую использовал очередной покупатель для оплаты; каждый номинал может принимать одно из четырёх значений: 5, 10, 50 или 100.

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

3 10 5 100
19
3 5 5 10
0
4 50 5 5 5
9

J: Заезд в лагерь

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

В первой строке входных данных через пробел записаны целые числа \(N\) и \(M\) (\(1 \le N \le 10^6, 1 \le M \le 1000\)). В следующей строке через пробел записаны \(M\) целых чисел в пределах от 1 до 1000 — вместимости автобусов.

В первой строке выведите число \(K\) — минимальное количество автобусов, которое придётся заказать. В следующей строке выведите через пробел \(M\) целых чисел — номера автобусов, которые нужно заказать. Автобусы пронумерованы от 1 до \(M\) в том порядке, в которых они перечислены во входных данных. Если возможных решений несколько, выведите любое. Если решения нет, в единственной строке выведите -1.

345 5 100 130 190 140 150
3 1 3 4
345 3 100 100 100
-1

K: Лексикографический порядок

Даны два списка чисел. Сравните их в лексикографическом порядке. Сами элементы списка сравниваются, как числа.

При решении этой задачи нельзя использовать стандартные операции языка Питон для сравнения списков (==, < и т.д.). Нельзя никак модифицировать данные списки, использовать вспомогательные списки.

Первая строка входных данных содержит два натуральных числа N и M. Во второй строке записаны через пробел N чисел: элементы первого списка. В третьей строке записаны через пробел M чисел: элементы второго списка.

Если списки совпадат, выведите слово equal. Если первый список меньше второго выведите слово less. Если первый список больше второго, выведите слово greater.

3 3 1 7 9 1 7 9
equal
3 4 1 2 3 1 2 10 11
less
3 2 3 2 1 3 2
greater

L: Тапочки

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

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

В первой строке входны данных записано число тапочков \(N\). Во второй строке записаны размеры тапочков в порядке слева направо, при этом левые тапочки условно обозначаются отрицательными числами (то есть \(-s\) обозначает левый тапочек, а \(s\) обозначает правый тапочек размера \(s\)).

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

6 -40 41 -42 -41 42 40
2

В примере подходят тапочки 40 размера (расстояние между ними равно 5) и 42 размера (расстояние между ними равно 2).

M: Абсолютный минимум температуры

Метеорологи ведут многолетние наблюдения за тем, в каком году была минимальная температура в данный день года. Например, абсолютный минимум температуры в Москве 8 марта был -32 градуса (1890).

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

Первая строка входных данных содержит два числа \(k\) и \(n\). Далее идет \(k\) строк, \(i\)-я строка содержит \(n\) чисел: значения температур для \(n\) дней наблюдений \(i\)-го года.

Программа должна вывести \(n\) чисел: миниальное значение температуры для каждого из дней наблюдений.

3 4 8 6 4 7 3 2 5 4 6 4 6 3
3 2 4 3

N: Долговые расписки

В одном карточном клубе состоит \(N\) джентльменов. Иногда азарт некоторых из них берет верх над благоразумием, и кто-то проигрывает больше денег, чем у него есть с собой. В этом случае проигравший обычно берет в долг у кого-то из посетителей клуба, чтобы расплатиться с партнерами по игре. Чтобы начать новый год «с чистого листа», джентльмены решили собраться в клубе и оплатить все долговые расписки, которые накопились у них друг к другу. Однако выяснилось, что иногда одни и те же джентльмены в разные дни выступали как в роли должников, так и в роли кредиторов. Поскольку истинные джентльмены считают мелочный подсчет денег ниже своего достоинства, то расчетами придется заняться вам.

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

Первая строка входных данных содержит сначала число \(N\) — количество джентльменов (натуральное, не превышает 100, не менее 2), и число \(K\) — количество долговых расписок (натуральное, не превышает 10000), после этого следует \(K\) троек чисел: номер джентльмена взявшего в долг, номер джентльмена давшего деньги и сумма. Номера джентльменов в расписках — натуральные числа, не превышающие \(N\). Сумма — натуральное число, не превышает 100. Гарантируется, что ни один джентльмен не брал в долг сам у себя.

Выведите N чисел — суммы, которые должны получить соответствующие джентльмены. Выведите положительное число, если этот джентльмен должен получить деньги от других, отрицательное — если он должен отдать деньги другим.

2 3 1 2 10 1 2 20 1 2 20
-50 50
3 1 3 1 100
100 0 -100

O: Наименьшее количество осадков

Даны результаты метеорологических наблюдений: количество осадков в каждый из 31 дня марта. Метеорологи хотят определить, какая из недель марта была наименее дождливой. Неделя — это семь дней с понедельника до воскресенья, то есть в марте может быть три или четыре полные недели.

Программа получает на вход 31 целое неотрицательное число через пробел: количество осадков для каждого из дней. В следующей строке записано число от 1 до 7: день недели, на который приходится 1 марта (1 означает понедельник, 2 вторник и так далее).

Программа должна определить неделю с наименьшим суммарными числом осадков и вывести суммарное число осадков на этой неделе.

0 4 3 3 4 4 6 2 4 8 3 1 4 5 8 1 6 3 8 4 6 2 9 4 0 5 4 5 1 8 0 4
28

Примечание к примеру. 1 марта — это четверг, поэтому первые четыре дня месяца пропускаются. Остаются следующие недели: 4 4 6 2 4 8 3 (сумма 31), 1 4 5 8 1 6 3 (сумма 28), 8 4 6 2 9 4 0 (сумма 33). Последние шесть дней месяца полной неделей не являются, поэтому не учитываются.

P: Антон решает задачи

Мальчик Антон решает вступительную работу в летний математический лагерь. В ней \(N\) заданий, которые можно выполнять в произвольном порядке. Разные задачи при этом могут требовать одинакового времени для решения. Известно, что если задание с номером \(i\) выполнять \(j\)-м по счету, Антону потребуется \(T_i\times j\) времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется \(T_1\times 1 + T_2\times2\) времени, а если выполнить сначала вторую задачу, а затем первую — то \(T_2\times 1 + T_1\times2\) . Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.

В первой строке входных данных записано число \(N\) (\(0\lt N \le 10\)). Во второй строке записаны числа \(T_1\), \(T_2\), ..., \(T_N\) через пробел. Все числа целые и удовлетворяют следующим ограничениям: \(0 \lt T_i \le 100\).

Требуется вывести сначала минимальное время, за которое можно решить все задачи, а затем — номера задач в том порядке, в котором их нужно решать, чтобы уложиться в это время. Если решений несколько, нужно выдать любое из них.

2 2 3
7 2 1

Q: Прыжки с трамплина

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

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

На вход подается 5 натуральных чисел от 1 до 20 , разделенных пробелом.

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

1 2 3 4 5
(1) 2 3 4 (5) = 9
10 11 10 11 10
(10) 11 10 (11) 10 = 31

R: Дома и магазины

На Новом проспекте построили подряд \(N\) зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

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

Первая строка входных данных содержит количество домов на Новом проспекте \(N\). Вторая строка содержит \(N\) чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина. Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом, то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между ними равно 2 и т.д.

10 2 0 1 1 0 1 0 2 1 2
3

S: Чемпионат по футболу

В чемпионате по футболу участвует \(N\) команд. Чемпионат проводится по круговой системе в один круг (каждые две команды сыграли один матч). Победитель матча получает 3 очка, проигравший: 0 очков, в случаи ничьи каждая из команд получает по 1 очку.

Даны результаты всех игр чемпионата. Постройте турнирную таблицу.

Программа получает на вход число команд \(N\ge 2\). В следующих \(N(N-1)/2\) строчках записаны результаты всех игр. Каждая строчка содержит 4 числа: номера команд \(a\) и \(b\), участвовавших в матче и результат матча (число голов, забитых командой \(a\) и командой \(b\)).

Определите число очков, набранной каждой командой. Отсортируйте список команд по невозрастанию числа набранных очков, а при равном числе очков — по возрастанию номера команды.

Выведите отсортированный список команд в \(N\) строчках. В каждой строке сначала записывается номер команды, потом число набранных ею очков.

4 1 2 2 2 3 4 0 0 1 3 3 0 2 4 0 3 1 4 0 2 2 3 1 1
4 7 1 4 2 2 3 2

T: Максимальная непрерывная сумма

В списке из \(N\) элементов, заполненном произвольными целыми числами, найдите непрерывный фрагмент, сумма чисел в котором максимальна, то есть найдите такие i и j, что сумма A[i]+A[i+1]+...+A[j] максимальна.

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

Программа должна вывести два индекса i и j таких, что сумма элементов от i-го до j-го максимальна. Если таких пар - несколько, то выведите ту пару, у которой j минимально возможное, а при равных j выведите ту пару, у которой i максимально возможно.

5 -1 2 3 -2 2
1 2
7 2 -2 3 -1 5 -2 7
2 6

U: Максимальная непрерывная сумма за \(O(n^2)\)

Решите предыдущую задачу при помощи алгоритма сложности \(O(n^2)\).

V: Симметричная последовательность

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

1 2 3 4 5 4 3 2 1

1 2 1 2 2 1 2 1

Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Программа получает на вход количество элементов исходной последовательности \(N\) \((1\le N\le 100)\). Далее идут \(N\) чисел — элементы этой последовательности, натуральные числа от 1 до 9.

Выведите сначала число \(M\) — минимальное количество элементов, которое надо дописать к последовательности, а потом \(M\) чисел (каждое от 1 до 9) — числа, которые надо дописать к последовательности.

9 1 2 3 4 5 4 3 2 1
0
5 1 2 1 2 2
3 1 2 1
5 1 2 3 4 5
4 4 3 2 1

W: Лавочки

Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).

Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.

В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

Во второй строке следуют K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка - это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края).

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

5 2 0 2
2
13 4 1 4 8 11
4 8
14 6 1 6 8 11 12 13
6 8

Второй пример соответствует лавочке на рисунке.

X: Ка-штаны

Как известно, обычно штаны состоят из двух штанин. Однако собачке нужны, например, уже штаны из 5 штанин (для 4-х лап и хвоста), а сороконожке – штаны с 40 штанинами.

У Пети живет Зверь, у которого M лап. Иногда – когда на улице особенно холодно, чтобы Зверь не простудился, на него бывает нужно надеть несколько штанов, чтобы на каждой лапе было надето по несколько штанин.

Петина мама оставила Пете N штанов, имеющих соответственно K1, K2, …, KN штанин, наказав ему надеть на Зверя их все. Петя хочет надеть на Зверя штаны так, чтобы на самой «утепленной» лапе оказалось как можно меньше штанин, но при этом все оставленные мамой штаны были надеты на зверя. Любые штаны можно надевать на любой набор лап (каждая лапа встречается в наборе не более одного раза).

Помогите ему – напишите программу, которая для каждых штанов укажет, на какие лапы должны быть надеты их штанины. Имейте в виду, что две штанины одних и тех же штанов не могут быть надеты на одну и ту же лапу (в то время как штанины разных штанов могут быть надеты на одну и ту же лапу).

Вводится сначала число M, а затем число N (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M).

Выведите N строк, в i-ой строке должно быть выведено Ki различных чисел, обозначающих номера лап Зверя, на которые должны быть надеты штанины i-ых штанов. Лапы Зверя нумеруются натуральными числами от 1 до M. Если искомых ответов несколько, то выведите любой из них.

4 3 1 2 3
1 1 2 2 3 4
Первые штаны надеты на лапу 1; вторые штаны надеты на лапы 1 и 2; третьи штаны надеты на лапы 2, 3 и 4. Таким образом, на самых «утепленных» лапах (а это лапы 1 и 2) надето по 2 штанины.
4 2 3 2
1 2 3 1 4
Первые штаны надеты на лапы 1, 2 и 3; вторые штаны надеты на лапы 1 и 4. Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2.

Y: Списывание

На контрольной работе \(N\) учеников сидят в ряд. Для каждого ученика известно, какую оценку он получил бы, если бы писал эту контрольную самостоятельно (оценка — это число от 2 до 5). Однако ученики могут писать контрольную не только самостоятельно, но и списывать у своего соседа, но только если сосед пишет контрольную самостоятельно. В этом случае списывающий получит такую же оценку, какую получит тот, у кого он списал.

А именно (правила применяются строго в указанном порядке):

Определите, кто какую оценку в итоге получит.

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

Выведите \(N\) чисел — оценки, которые получат ученики за контрольную.

5 5 2 3 4 5
5 5 3 5 5
Первый и пятый ученики будут писать самостоятельно. Второй спишет у первого, а четвертый — у пятого (в итоге также получат пятерки). Третьему не у кого списывать, так как его соседи будут писать работу не самостоятельно.
6 2 2 3 2 2 4
2 3 3 3 4 4
Второй и четвертый спишут у третьего, пятый — у шестого.