Алгоритмы сортировки

На числовой прямой даны \(n\) отрезков. Требуется разбить их на минимальное число групп так, чтобы внутри каждой группы любые два отрезка не пересекались. При этом стыковка концом-к-началу пересечением не считается: отрезки \([a, b]\) и \([b, c]\) могут попасть в одну группу.

Найдите минимальное возможное число групп.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(0 \le l_i < r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — минимум групп.

Примечание

В первом примере отрезки \([0, 30]\), \([5, 10]\), \([15, 20]\), \([25, 35]\). В одну группу можно положить \([5, 10]\), \([15, 20]\) и \([25, 35]\) — они попарно не пересекаются. Отрезок \([0, 30]\) пересекается с каждым из них и требует отдельной группы. Итого: \(2\).

Во втором примере отрезки \([10, 20]\) и \([20, 30]\) стыкуются по точке \(20\), и по условию это не считается пересечением. Поэтому одной группы достаточно.

На числовой прямой задан целевой отрезок \([L, R]\) и \(n\) отрезков-«покрывал». Определите, покрывают ли эти \(n\) отрезков целевой отрезок целиком — то есть каждая точка из \([L, R]\) принадлежит хотя бы одному из них.

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

В первой строке — два целых числа \(L\) и \(R\) (\(-10^9 \le L \le R \le 10^9\)) — концы целевого отрезка.

Во второй строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка-покрывала.

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

Выведите YES, если каждая точка целевого отрезка \([L, R]\) покрыта хотя бы одним из данных отрезков, и NO иначе.

Примечание

В первом примере отрезки \([0, 4]\), \([3, 7]\), \([6, 10]\) вместе покрывают всю цель \([0, 10]\) без пропусков.

Во втором примере между точками \(4\) и \(6\) есть пропуск (точка \(5\) не покрыта ни одним отрезком), поэтому ответ NO.

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

Найдите суммарную длину закрашенной части прямой.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — длина объединения всех данных отрезков.

Примечание

В первом примере отрезки \([1, 5]\) и \([3, 7]\) сливаются в один отрезок \([1, 7]\) длины \(6\). Отдельный отрезок \([10, 12]\) добавляет ещё \(2\). Итого: \(8\).

Во втором примере четыре отрезка стыкуются концом-к-началу и образуют один сплошной отрезок \([0, 4]\) длины \(4\).

На числовой прямой нарисованы \(n\) отрезков. Концы отрезков заданы целыми числами. Точка \(x\) считается принадлежащей отрезку \([s, f]\), если \(s \le x \le f\) (концы включены).

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

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

В первой строке записано целое число \(n\) (\(1 \le n \le 10^5\)) — количество отрезков.

В каждой из следующих \(n\) строк записаны два целых числа \(s_i\) и \(f_i\) (\(-10^9 \le s_i \le f_i \le 10^9\)) — концы очередного отрезка.

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

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

Примечание

В первом примере отрезки \([0,1]\), \([0,2]\), \([1,2]\). Точка \(x = 1\) принадлежит всем трём отрезкам, и это наименьшая такая точка.

Во втором примере точка \(x = 1\) принадлежит двум отрезкам: \([0,1]\) и \([1,3]\). Это максимум, достигаемый раньше всего на прямой.

Ночью на сибирской трассе одновременно сошло \(n\) снежных заносов. Каждый занос перекрывает участок дороги между километровыми отметками \(a_i\) и \(b_i\) включительно. Сообщения о заносах поступали диспетчеру по рации в произвольном порядке, поэтому \(a_i\) может оказаться как меньше, так и больше \(b_i\): занос покрывает все километровые отметки от \(\min(a_i, b_i)\) до \(\max(a_i, b_i)\) включительно.

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

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

В первой строке записаны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 50\,000\)) — количество заносов и количество запросов.

В следующих \(n\) строках записаны по два целых числа \(a_i\) и \(b_i\) (\(-10^9 \le a_i, b_i \le 10^9\)) — концы участка \(i\)-го заноса в произвольном порядке.

В последней строке через пробел записаны \(m\) целых чисел \(p_1, p_2, \ldots, p_m\) (\(-10^9 \le p_j \le 10^9\)) — километровые отметки, о которых спрашивают водители.

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

Выведите \(m\) целых чисел через пробел: для каждой отметки \(p_j\) — количество заносов, перекрывающих этот километр.

Примечание

Точка считается принадлежащей участку с концами \(a\) и \(b\), если выполняется неравенство \(\min(a, b) \le p \le \max(a, b)\). Совпадение с границей засчитывается.

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

На вход подаётся число \(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\)).

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

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