Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Ханойская фабрика#49297

Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.

На складах фабрики находятся \(n\) колец, \(i\)-е кольцо имеет внутренний радиус \(a_i\), внешний радиус \(b_i\) и высоту \(h_i\). Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:

Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j \leq b_i\).
Кольца не должны проваливаться друг в друга, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j > a_i\).
Суммарная высота всех использованных колец должна быть максимальна.

Формат входных данных
В первой строке входных данных записано целое число \(n\) (\(1 \leq n \leqslant 100\,000\)) — количество колец на складах фабрики.

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

Формат выходных данных
Выведите максимальную высоту башни, которую смогут получить работники фабрики.

Замечание

В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке \(3\), \(2\), \(1\).

Во втором примере можно либо поставить кольцо \(3\) на кольцо \(4\) и получить башню высоты \(3\), либо поставить кольцо \(1\) на кольцо \(2\) и получить башню высоты \(4\).

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решение, корректно работающие при \(1 \leq n \leq 9\), наберут не менее \(10\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 15\), наберут не менее \(20\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 1000\), наберут не менее \(60\) баллов.

✓ 1✗ 3—Войти и решать

Игра "Банковские карты"#49294

После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру “Банковские карты”.

Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с \(n\)-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если \(n=3\) и у Шерлока номер карты \(123\), а у Мориарти \(321\), то сначала Шерлок называет число \(1\), а Мориарти называет число \(3\) и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число \(2\), и щелбан не получает никто. Наконец на третьем шаге, Шерлок называет \(3\), а Мориарти называет \(1\) и получает щелбан.

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

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

Формат входных данных
В первой строке находится одно целое число \(n\) (\(1 \leqslant n \leqslant 1000\)) — количество цифр в банковских картах Шерлока и Мориарти.

Во второй строке записана последовательность из \(n\) цифр — номер кредитной карточки Шерлока.

В третьей строке записана последовательность из \(n\) цифр — номер кредитной карточки Мориарти.

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

Во второй строке выведите так же одно число — максимальное число щелбанов, которое Мориарти может дать Шерлоку.

Замечание
Первый примерс овпадает с примером разобранным в условии задачи. Во втором примере Мориарти никак не сможет избежать двух щелбанов

Решения, корректно работающие при \(1 \leq n \leq 3\), наберёт не менее \(10\) баллов.

Решения, корректно работающие при \(1 \leq n \leq 8\), наберет не менее \(30\) баллов.

Разные системы счисления Сортировка подсчетом

✓ 3✗ 141 000средняяВойти и решать

Сортировка выбором#49138

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

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

Выходные данные
Вывести получившийся массив.

Пример

№	Входные данные	Выходные данные
1	5 5 4 3 2 1	1 2 3 4 5

Сортировка вставками

✓ 796✗ 830300лёгкаяВойти и решать

Средние по росту#49039

Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел m_i - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

Формат выходных данных
Напечатайте среднее арифметическое роста тех двоих людей, которые бы оказались в середине шеренги в случае построения ее по росту, начиная с самого низкого. Ваш ответ будет проверяться с точностью 10^-6.

Квадратичные сортировки

✓ 201✗ 244400лёгкаяВойти и решать

Самый легкий#49037

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел m_i - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵). В третьей строке записано натуральное число k (k ≤ n).

Формат выходных данных
Напечатайте массу предмета, являющегося "k-м самым легким предметом".

Квадратичные сортировки

✓ 125✗ 286400лёгкаяВойти и решать

K-й по счету#49035

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел v_i - значения максимальной скорости i-го автомобиля (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵). В третьей строке записано натуральное число k (k ≤ n).

Формат выходных данных
Напечатайте максимальную скорость автомобиля, являющегося "k-м самым быстрым автомобилем".

Квадратичные сортировки

✓ 106✗ 136400лёгкаяВойти и решать

Тестирование мессенджера - 2#49030

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

генерируется случайный сценарий взаимодействия пользователей с приложением;
в приложении симулируется выполнение этого сценария;
проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

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

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

Формат входных данных
В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.
События второго набора задаются в формате <<CHANGE \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.
События третьего набора задаются в формате <<SEND FROM \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

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

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество полученных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, от которого он получил больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, полученных от пользователя \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не получал сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

Задача на реализацию Сортировка событий Хеш

✓ 1✗ 2—Войти и решать

Тестирование мессенджера#49029

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

генерируется случайный сценарий взаимодействия пользователей с приложением;
в приложении симулируется выполнение этого сценария;
проверяется корректность итогового состояния приложения.

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

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

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

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

В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

События первого набора задаются в формате <<\(t_i\): REG \(\mathtt{id}_i\) \(\mathtt{handle}_i\)>>.
События второго набора задаются в формате <<\(t_i\): CHANGE \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.
События третьего набора задаются в формате <<\(t_i\): SEND \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> SENT <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> TO <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество отправленных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, получившего от него больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, отправленных пользователю \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, получивших от него максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не отправлял сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

реализация Сортировка событий Хеш

✓ 1✗ 2—Войти и решать

Парковка - 2#49026

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

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

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i \le t^\mathrm{in}_j\) и \(t^\mathrm{out}_i \ge t^\mathrm{out}_j\).

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

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

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

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

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(n\) строках перечислены времена въезда и выезда для каждого сотрудника, в \(i\)-й строке через пробел \(t^\mathrm{in}_i\) и \(t^\mathrm{out}_i\) (\(1 \le t^\mathrm{in}_i, t^\mathrm{out}_i \le 10^9\)).

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

В первой строке выведите число \(k\) — минимальное необходимое количество рядов.

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

Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.

Жадный алгоритм Использование сортировки

✓ 2✗ 0—Войти и решать

Обувной магазин#48947

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

Формат входных данных
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.

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

Квадратичные сортировки

✓ 0✗ 31 200средняяВойти и решать

Такси#48945

Наши люди до метро на такси не ездят!

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин — ровно столько, сколько у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

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

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

Сначала во входном файле записано натуральное число N (1 ≤ N ≤ 1000) — количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число — для первого сотрудника, второе — для второго и т.д.). Все расстояния — положительные целые числа, не превышающие 1000. Далее записано еще N чисел — тарифы за проезд одного километра в такси (первое число — в первой машине такси, второе — во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.

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

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

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

✓ 63✗ 123700средняяВойти и решать

Результаты олимпиады#48944

В олимпиаде участвовало N человек. Каждый получил определенное количество баллов, при этом оказалось,что у всех участников — разное число баллов.

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

Формат входных данных
Программа получает на вход число участников олимпиады N. Далее идет N строк, в каждой строке записана фамилия участника, затем, через пробел, набранное им количество баллов.

Формат входных данных
Выведите список участников (только фамилии) в порядке убывания набранных баллов.

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

✓ 181✗ 161600лёгкаяВойти и решать

Минимизируем число#48942

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

Формат входных данных
Вводится натуральное четырехзначное число.

Формат выходных данных
Выведите минимальное натуральное четырехзначное число, состоящее из тех же цифр.

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

✓ 154✗ 396500лёгкаяВойти и решать

Вечер кёрлинга#48049

Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени l_i и заканчивается в момент времени r_i.

Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени r_i, то она может после него посмотреть любой матч j, который начинается не раньше момента времени r_i, то есть l_j > r_i (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию l_j - r_i => t. Перерыв не может быть до или после всех просмотренных игр.

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

Формат входных данных
Первая строка входных данных содержит число n (2 ≤ n ≤ 100 000) - количество показываемых матчей.
Вторая строка входных данных содержит число t (1 ≤ n ≤ 10⁹) - минимальная длина перерыва, который должна сделать Василиса.
В следующих n строках содержится по два числа l_i и r_i ( 1 ≤ l_i < r_i ≤ 10⁹) - начало и конец i-го матча.

Формат выходных данных
Программа должна вывести число m - максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел - номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы t, то выведите число -1.

Замечание
В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6,
который заканчивается в момент времени 4, потом переключится на матч 3, который продолжается с 4 до 6.
Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3.

Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t=5, нельзя.

Жадный алгоритм Использование сортировки

✓ 5✗ 451 100средняяВойти и решать

Детские подарки#47970

Вы замечательный родитель и хотите подарить детям подарки. Но, чтобы не избаловать своих детей, вы должны дать каждому ребенку не более одного подарка.
Каждый ребенок i имеет уровень ожидания равный g[i] - целое число, показывающее минимальный размер подарка, получив который ребенок обрадуется. Каждый подарок j имеет размер s[j].
Посчитайте, какое максимальное количество детей вы сможете обрадовать.

Входные данные
Первая строка содержит целое число n - количество детей. Вторая строка содержит n целых чисел g[i] - уровень ожидания i-го ребенка. В третьей строке записано число m - количество подарков. Четвертая строка содержит m целых чисел s[j] - размер j-го подарка.

Ограничения

1 <= n <= 3 * 10⁴
0 <= m <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 1

Выходные данные
Выведите одно число. Ответ на задачу

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

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

✓ 35✗ 235800средняяВойти и решать

Максимус спасает Элстейд#47509

Одарённый невероятной магией и всезнанием Максимус заметил группу из n монстров, приближающихся к городку Элдстейд. Своими волшебными способностями он мгновенно определил расстояние в километрах от города до каждого монстра. Он также заметил, что все монстры двигаются с постоянной скоростью. У Максимуса есть оружие, способное уничтожить одного монстра после полной зарядки. Зарядка занимает ровно одну минуту. Чтобы победить монстра, оружие должно быть полностью заряжено к моменту приближения монстра к городу. Другими словами, невозможно убить монстра достигшего города, даже если в этот момент оружие закончило полную зарядку.
Максимус задается вопросом, сможет ли он сам спасти город от всех монстров или ему нужна помощь.
Напишите программу, которая поможет Максимусу мгновенно определить максимальное количество монстров, которое он сможет уничтожить до того момента, как хотя бы один монстр достигнет города.

Входные данные
Первая строка содержит число n - количество монстров. Во второй строке записано n чисел dist[i] - начальное расстояние в километрах от города для i-го монстра. Третья строка содержит n чисел speed[i] - скорость i-го монстра в километрах в минуту.

Ограничения

n == длина массива dist == длина массива speed
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Примечание
1	3 1 3 4 1 1 1	3	Вначале расстояния между монстрами равны [1,3,4]. Максимус уничтожает первого монстра. Через минуту расстояния между монстрами становятся [X,2,3]. Максимус уничтожает второго монстра. Через минуту расстояния между монстрами будут [X,X,2]. Максимус уничтожает третьего монстра. Все три монстра могут быть уничтожены.
2	4 1 1 2 3 1 1 1 1	1	Вначале расстояния между монстрами равны [1,1,2,3]. Максимус уничтожает первого монстра. Через минуту расстояния между монстрами становятся равными [X,0,1,2], и второй монстр достиг города. Максимус может уничтожить только 1 монстра.

Алгоритмы сортировки Жадный алгоритм Массивы

✓ 40✗ 171800средняяВойти и решать

Сортировка строки по частоте букв#46034

Дана строка s. Отсортируйте символы данной строки в порядке убывания частоты встречаемости. Частота встречаемости символа - это количество раз, которое данный символ встречается в строке.

Выведите отсортированную строку. Если два символа встречаются одинаковое количество раз, то они должны идти в лексикографическом порядке.

Входные данные
Программа получает на вход

Ограничения
1 <= s.length <= 5 * 10⁵(s.length - длина строки s)
s содержит большие и маленькие английские буквы и цифры.

Выходные данные
Выведите отсортированную строку.

Примеры

№	Входные данные	Выходные данные
1	tree	eert
2	cccaaa	aaaccc
3	Aabb	bbAa

Сортировка подсчетом Строки

✓ 52✗ 186800средняяВойти и решать

Первый уникальный#46033

Символ называется уникальным, если он встречается в строке один раз. Первый уникальный символ - это уникальный символ с наименьшим индексом.
Дана строка s. Найдите первый уникальный символ в данной строке. Выведите его индекс. Если в строке нет уникальных символов, выведите -1.

Входные данные
Программа получает на вход последовательность непробельных символов s.

Ограничения
'a' <= s[i] <= 'z'
0 <= i <= 255

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	silvertests	1
2	sstt	-1

Сортировка подсчетом Строки

✓ 109✗ 210600лёгкаяВойти и решать

Сортировка строк матрицы по половинам#46032

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

Входные данные
В первой строке записаны два целых числа N и M - количество строк и столбцов матрицы соответственно. Далее идет N строк, каждая из которых содержит по M чисел, разделенных одним пробелом - элементы массива (nums).

Ограничения
1 <= N, M <= 10³
-10⁹ <= nums_i,j <= 10⁹

Выходные данные
Выведите отсортированный массив.

Примеры

№	Входные данные	Выходные данные
1	3 5 4 0 2 1 3 1 3 2 0 0 1 1 2 1 1	1 1 2 1 1 1 3 2 0 0 4 0 2 1 3

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

✓ 95✗ 184700средняяВойти и решать

Сортировка матрицы по сумме строк#46031

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

Входные данные
В первой строке записаны два целых числа N и M - количество строк и столбцов матрицы соответственно. Далее идет N строк, каждая из которых содержит по M чисел, разделенных одним пробелом - элементы массива (nums).

Ограничения
1 <= N, M <= 10³
-10⁹ <= nums_i,j <= 10⁹

Выходные данные
Выведите отсортированный массив.

Примеры

№	Входные данные	Выходные данные
1	3 3 4 0 2 1 3 2 1 1 2	1 1 2 1 3 2 4 0 2

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

✓ 139✗ 219600лёгкаяВойти и решать