Алгоритмы поиска

Примеры

№	Входные данные	Выходные данные
1	2.0000000000	1.000000000
2	18.0000000000	4.000000000

Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — d_t , здоровье — h единиц.

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

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

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*10⁵),  d_e, d_t , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( d_e, d_t , h <= 10⁹). В следующей строке задано n натуральных чисел a_i — число единиц здоровья i-го солдата армии противника (a_i <= 10⁹).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.
 

Ввод	Вывод
3 3 1 1 2 1 2 3	3
4 10 2 1 2 1 2 1 2	5
3 1 1 2 5 1 2 3	-1

Алекс настраивает связь между исследовательскими станциями. Есть n станций и m возможных двусторонних каналов. Канал между станциями u и v начинает работать, если общая настройка мощности P не меньше указанного для него порога w.

Сообщение нужно передать со станции s на станцию t, использовав не более k каналов подряд. Использование одного канала считается одним переходом. Промежуточные станции могут пересылать сообщение.

Найдите минимальную целую мощность P ≥ 0, при которой это возможно. Если подходящего маршрута нет даже при работающих всех каналах, сообщите об этом.

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

Первая строка содержит пять целых чисел n, m, k, s, t (2 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n − 1, 1 ≤ s, t ≤ n, s ≠ t).

Следующие m строк содержат u, v, w (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 10⁹). Между одной парой станций не более одного канала.

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

Выведите минимальную мощность либо −1, если передать сообщение за допустимое число переходов невозможно.

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

Пример 1. При мощности 7 подходит маршрут 1 → 3 → 5. При мощности 6 доступен маршрут 1 → 3 → 4 → 5, но он слишком длинный.

Пример 2. Связь существует, но сообщение должно пройти два канала, а разрешён только один.

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

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

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

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

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

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

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

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

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

На научной смене Алекс может посетить n лабораторных сеансов. Сеанс i начинается в момент sᵢ, заканчивается в момент fᵢ и приносит vᵢ исследовательских баллов. Баллы начисляются только за полностью посещённый сеанс.

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

Алекс может выбирать любые сеансы и пропускать остальные. Найдите максимальную сумму баллов.

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

Первая строка содержит целое число n (1 ≤ n ≤ 200 000). Следующие n строк содержат по три целых числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 10⁹, 1 ≤ vᵢ ≤ 10⁹). Сеансы перечислены в произвольном порядке; совпадения времён допускаются.

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

Выведите максимальное количество баллов, которое сможет набрать Алекс.

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

Пример 1. Подходят сеансы 1, 3 и 5: 7 + 9 + 10 = 26 баллов.

Пример 2. Окончание первого совпадает с началом второго; можно посетить оба.

К фестивалю Алекс готовит k значков. В мастерской работают n независимых станков. В момент 0 Алекс включает их все.

Станок i сначала прогревается sᵢ секунд, затем изготавливает один значок за pᵢ секунд. Его первый значок готов в момент sᵢ + pᵢ, второй — в момент sᵢ + 2pᵢ и так далее. Между значками станок не останавливается. Материалов достаточно.

Найдите самый ранний целый момент времени, когда суммарно будет готово не менее k значков. Значок, завершённый ровно в этот момент, уже считается готовым.

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

Первая строка содержит целые числа n и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10⁹).

Следующие n строк содержат по два целых числа sᵢ и pᵢ (0 ≤ sᵢ ≤ 10⁹, 1 ≤ pᵢ ≤ 10⁹).

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

Выведите одно целое число — искомый момент времени в секундах.

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

Пример 1. К моменту 8 готовы 2 + 2 = 4 значка, а к моменту 9 — 3 + 2 = 5.

Пример 2. Значки единственного станка готовы в моменты 9, 13 и 17.

Алекс выбирает мастер-классы научного фестиваля. Мастер-класс i идёт с момента sᵢ до момента fᵢ и приносит vᵢ баллов опыта. Чтобы получить баллы, его нужно посетить целиком.

Абонемент Алекса позволяет посетить не более K мастер-классов. Одновременно находиться на двух нельзя. Если один закончился ровно в момент начала другого, можно посетить оба. Переходы между аудиториями мгновенны.

Найдите максимальную сумму баллов опыта, которую можно получить с этим абонементом.

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

Первая строка содержит целые числа n и K (1 ≤ n ≤ 50 000, 1 ≤ K ≤ min(30, n)). Следующие n строк содержат целые числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 10⁹, 1 ≤ vᵢ ≤ 10⁹). Порядок произвольный; совпадения времён допустимы.

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

Выведите максимальную сумму баллов.

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

Пример 1. Лучше посетить только шестой мастер-класс. Цепочка 1, 3, 5 дала бы 26 баллов, но требует трёх посещений.

Пример 2. Из трёх совместимых мастер-классов нужно выбрать два: второй и третий.

Алекс должен перевезти n ящиков с экспонатами. На складе ящики стоят в очереди, массы ящиков равны a₁, …, aₙ.

За один рейс Алекс забирает несколько первых оставшихся ящиков. Менять порядок и пропускать ящики нельзя. Каждый ящик перевозится целиком, ровно один раз. Масса груза в одном рейсе не должна превышать грузоподъёмность машины C.

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

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

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

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

Выведите минимальную грузоподъёмность.

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

Пример 1. Подходят рейсы [4, 2], [7], [3, 5]. При грузоподъёмности 7 понадобятся четыре рейса.

Пример 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 останется.

Учительница литературы просит помечать тавтологии — когда одно и то же слово стоит подряд два раза: «был был», «очень очень».

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

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Слово — это последовательность букв (кириллица или латиница), цифр и подчёркиваний.

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

Тот же текст, но каждое повторение подряд двух одинаковых слов обёрнуто в квадратные скобки: [слово слово]. Пунктуация и все остальные символы сохраняются.

Примечание

Регистр при сравнении слов не учитывается: Очень очень — тоже повтор. В выводе регистр оригинала сохраняется.

В заметках на телефоне ты ведёшь дневник тренировок. Даты писали по-разному: 17.04.2026, 17/04/2026, 17-04-2026, 17 апреля 2026.

Приведи все найденные даты к ISO-формату YYYY-MM-DD.

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Формат даты: день (1–2 цифры), разделитель (., /, - или пробел), месяц (2 цифры или слово на русском), разделитель, год (4 цифры).

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

Каждая найденная дата в формате YYYY-MM-DD на отдельной строке в порядке появления.

Примечание

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

Мама выгрузила из электронного дневника текстовую выписку. Каждая строка выглядит так: название предмета, двоеточие, оценки через запятую или пробел.

Напиши программу, которая для каждого предмета посчитает средний балл.

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

Одна или несколько строк вида Название предмета: оценки. Название предмета — одно или несколько русских слов (только буквы и пробелы). Оценки — целые числа от 2 до 5, разделённые запятыми и/или пробелами.

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

Для каждого предмета в том же порядке, в котором они встретились во входе, выведи строку вида Предмет: X.XX — название, двоеточие, пробел, средний балл с двумя знаками после точки.

Примечание

Используй округление Python по умолчанию (функция round). Предметы без оценок (если такие попадутся) в выводе пропускай.

В Telegram-чате класса ребята обращаются друг к другу через @никнейм. Ты — староста и хочешь понять, кого упоминают чаще всех.

Никнейм — это символ @, за которым идут от 5 до 32 символов: латинские буквы, цифры и подчёркивания. Короткие последовательности (меньше 5 символов) никнеймами не считаются.

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

В первой строке — число \(N\) (\(1 \le N \le 100\)) — сколько самых упоминаемых никнеймов нужно вывести.
Далее — произвольный текст чата до 10 000 символов.

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

Топ-\(N\) никнеймов в нижнем регистре, каждый на отдельной строке. Порядок — по убыванию частоты упоминаний; при равенстве частот раньше идёт тот, кто первым встретился в тексте.

Если уникальных никнеймов меньше \(N\), выведи все, что есть.

Примечание

Регистр при подсчёте игнорируется: @Katya и @katya — один человек.

Ты ведёшь паблик класса во ВКонтакте и хочешь собирать статистику по хештегам.

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

Хештег — это символ #, за которым идут один или более символов: буквы (латиница или кириллица), цифры или подчёркивания.

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

Произвольный текст от одной до 100 строк, общей длиной не более 10 000 символов.

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

Каждый найденный хештег на отдельной строке в порядке появления в исходном тексте.