Использование сортировки

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

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

Входные данные

Первая строка содержит целые числа n и k (2 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n различных целых координат xᵢ (0 ≤ xᵢ ≤ 10⁹) в произвольном порядке.

Выходные данные

Выведите максимальное минимальное расстояние.

Пояснения к примерам

Пример 1. Можно поставить датчики в точках 1, 4 и 8. Минимальное расстояние равно 3.

Пример 2. Нужно занять оба места.

Алекс готовит приборы к экспедиции. Для включения одного прибора нужны ровно два аккумулятора с суммарным зарядом не меньше L. Аккумуляторы могут иметь разный заряд.

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

Входные данные

Первая строка содержит целые числа n и L (2 ≤ n ≤ 200 000, 1 ≤ L ≤ 2·10⁹). Вторая строка содержит n целых зарядов aᵢ (1 ≤ aᵢ ≤ 10⁹).

Выходные данные

Выведите максимальное количество включённых приборов.

Пояснения к примерам

Пример 1. Подходят пары зарядов (1, 9), (2, 8), (3, 7).

Пример 2. Можно использовать пары (3, 9) и (4, 8); аккумулятор с зарядом 2 останется.

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

Для того чтобы собрать прямоугольную грядку, нужны 4 доски. В идеале это должны быть две пары досок равной длины, тогда из них можно сложить ровный прямоугольник. Но если доски имеют неравную длину, то в одном из углов полученной грядки можно разместить пластиковый уголок: две планки длины \(r\), скреплённые под прямым углом. Уголок со стороной \(r\) позволит увеличить длины двух досок на величину, не превосходящую \(r\). Если противоположными сторонами грядки будут доски длины \(a\) и \(b\), а также \(c\) и \(d\) соответственно, то для того чтобы сделать прямоугольную грядку из этих досок, понадобится уголок размера \(\max(|a-b|, |c-d|)\) . Например, чтобы сделать грядку из досок длины 5, 7, 3, 2, понадобится уголок размера 2. На рисунке чёрным цветом изображены доски и красным цветом изображён уголок.

В сарае у Аркадия Аркадьевича нашлись \(n\) досок, \(i\)-я из которых имеет длину \(l_i\). Теперь он хочет выбрать из них четыре и сложить из них грядку таким образом, чтобы использовать уголок наименьшего размера. Помогите ему.

Первая строка входных данных содержит число \(n\) (\(4 \leq n \leq 10^5\)) — количество досок в сарае у Аркадия Аркадьевича.

Следующие \(n\) строк содержат числа \(l_1, \dots, l_n\) (\(1 \leq l_i \leq 10^9\)) — длины досок.

Программа должна сначала вывести число \(r\) — минимально возможный размер уголка.

Во второй строке выведите 4 числа \(a\), \(b\), \(c\), \(d\)  — длины досок, которые необходимо выбрать для грядки. При этом противоположными сторонами прямоугольника будут доски \(a\) и \(b\), а также \(c\) и \(d\). Если есть разные варианты выбора досок для грядки с одной и той же величиной уголка, можно вывести любой из них.

Решения, правильно работающие, когда \(n \leq 30\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(n \leq 100\), будут оцениваться в 45 баллов.

Решения, правильно работающие, когда \(n \leq 500\), будут оцениваться в 65 баллов.

Решения, правильно работающие, когда все \(l_i \leq 30\), будут оцениваться в 10 баллов.

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

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

Программа должна:

• Разбить слова на группы анаграмм
• Вывести каждую группу, в которой больше одного слова
• Группы отсортировать по убыванию размера. При равном размере — по алфавиту первого слова
• Слова внутри группы — в алфавитном порядке, через пробел

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 30\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы).

Формат выходных данных

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

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

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

Программа должна:

• Разбить слова на группы анаграмм
• Вывести каждую группу, в которой больше одного слова
• Группы отсортировать по убыванию размера. При равном размере — по алфавиту первого слова
• Слова внутри группы — в алфавитном порядке, через пробел

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 30\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы).

Формат выходных данных

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

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

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

Программа должна:

• Разбить слова на группы анаграмм
• Вывести каждую группу, в которой больше одного слова
• Группы отсортировать по убыванию размера. При равном размере — по алфавиту первого слова
• Слова внутри группы — в алфавитном порядке, через пробел

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 30\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы).

Формат выходных данных

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

Примечание

Подсказка: два слова — анаграммы, если при сортировке их букв получается одинаковый результат. Например, sorted("кот") и sorted("ток") оба дают ['к', 'о', 'т'].

Учитель ведёт журнал сдачи домашних заданий. На вход подаётся число \(N\) — количество записей. Затем \(N\) строк в формате:

имя предмет балл

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

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

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 30\)).

Следующие \(N\) строк — имя, предмет и балл через пробел.

Формат выходных данных

Для каждого ученика строка в формате: Имя — X заданий, Y баллов

На соревнованиях по прыжкам в длину зафиксированы результаты спортсменов. На вход подаётся число \(N\) — количество спортсменов. Затем вводятся \(N\) целых чисел (каждое с новой строки) — дальность прыжка в сантиметрах.

Программа должна:

• Собрать все числа в список
• Отсортировать список по возрастанию
• Вывести отсортированный список
• Вывести три наибольших значения (последние 3 элемента отсортированного списка)

Формат входных данных

Первая строка — целое число \(N\) (\(3 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от 100 до 900).

Формат выходных данных

Первая строка — отсортированный список в формате [a, b, c, ...].

Вторая строка — три наибольших значения в формате Топ-3: [x, y, z].

Метеостанция записала температуру за несколько дней. На вход подаётся число \(N\) — количество дней. Затем вводятся \(N\) целых чисел (каждое с новой строки) — температура каждого дня.

Программа должна:

• Собрать все числа в список
• Отсортировать список по возрастанию
• Вывести отсортированный список
• Вывести три наибольших значения (последние 3 элемента отсортированного списка)

Формат входных данных

Первая строка — целое число \(N\) (\(3 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от \(-50\) до \(50\)).

Формат выходных данных

Первая строка — отсортированный список в формате [a, b, c, ...].

Вторая строка — три наибольших значения в формате Топ-3: [x, y, z].

В школе прошёл экзамен. На вход подаётся число \(N\) — количество учеников. Затем вводятся \(N\) целых чисел (каждое с новой строки) — баллы учеников.

Программа должна:

• Собрать все числа в список
• Отсортировать список по возрастанию
• Вывести отсортированный список
• Вывести три наибольших значения (последние 3 элемента отсортированного списка)

Формат входных данных

Первая строка — целое число \(N\) (\(3 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от 0 до 100) — балл ученика.

Формат выходных данных

Первая строка — отсортированный список в формате [a, b, c, ...].

Вторая строка — три наибольших значения в формате Топ-3: [x, y, z].

Пользователь вводит количество слов, а затем сами слова — каждое на отдельной строке. Сохраните все слова в список.

Выведите две строки:

1. Исходный список — слова через пробел в порядке ввода.
2. Отсортированный список — слова через пробел по возрастанию длины. Если длины равны, сохраните порядок ввода.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 15\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы, без пробелов).

Формат выходных данных

Две строки: исходный список и отсортированный по возрастанию длины, слова через пробел.

Примечание

Подсказка: используйте key=len в функции sorted().

Пользователь вводит количество чисел, а затем сами числа — каждое на отдельной строке. Сохраните все числа в список.

Выведите две строки:

1. Исходный список — числа через пробел в порядке ввода.
2. Отсортированный список — числа через пробел по возрастанию их модуля (абсолютного значения). Если модули равны, сохраните порядок ввода.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от \(-1000\) до \(1000\)).

Формат выходных данных

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

Примечание

Модуль числа — это число без знака. Например, модуль числа \(-7\) равен \(7\), модуль числа \(3\) равен \(3\).

Подсказка: используйте key=abs в функции sorted().

Пользователь вводит количество слов, а затем сами слова — каждое на отдельной строке. Сохраните все слова в список.

Выведите две строки:

1. Исходный список — слова через пробел в порядке ввода.
2. Отсортированный список — слова через пробел в алфавитном порядке.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 15\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы, без пробелов).

Формат выходных данных

Две строки: исходный список и отсортированный по алфавиту, слова через пробел.

Пользователь вводит количество чисел, а затем сами числа — каждое на отдельной строке. Сохраните все числа в список.

Выведите две строки:

1. Исходный список — числа через пробел в порядке ввода.
2. Отсортированный список — числа через пробел по убыванию.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от \(-1000\) до \(1000\)).

Формат выходных данных

Две строки: исходный список и отсортированный по убыванию, числа через пробел.

Пользователь вводит количество чисел, а затем сами числа — каждое на отдельной строке. Сохраните все числа в список.

Выведите две строки:

1. Исходный список — числа через пробел в порядке ввода.
2. Отсортированный список — числа через пробел по возрастанию.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от \(-1000\) до \(1000\)).

Формат выходных данных

Две строки: исходный список и отсортированный по возрастанию, числа через пробел.

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

Формат входных данных

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

Формат выходных данных

Три строки:

1. Минимальное число.
2. Максимальное число.
3. Все числа в порядке возрастания через пробел.

Пользователь вводит несколько имён через пробел в одной строке. Выведите их в алфавитном порядке.

Формат входных данных

Одна строка — имена через пробел (от 2 до 15 имён). Все имена начинаются с заглавной буквы, остальные строчные. Имена состоят только из русских букв.

Формат выходных данных

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

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

Формат входных данных

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

Формат выходных данных

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

Пользователь вводит несколько целых чисел в одной строке через пробел. Выведите их в порядке возрастания.

Формат входных данных

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

Формат выходных данных

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

Пользователь вводит несколько слов через пробел. Постройте словарь, где ключ — слово, значение — его длина. Выведите пары в формате слово: длина, отсортированные по длине в порядке возрастания. Если длины одинаковые, сортируйте по алфавиту.

Формат входных данных

Одна строка — слова через пробел (от 2 до 15 слов). Все слова различны.

Формат выходных данных

Строки в формате слово: длина, отсортированные по длине (по возрастанию), при равенстве — по алфавиту.