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

Маяк 5. Последний опасный замер

Экспедиция «МАЯК». Перед стартом исследовательского модуля тепловые замеры отсортировали от самой высокой температуры к самой низкой. Одинаковые показания встречаются несколько раз. Тревога включается только при значении строго выше x, а ровно x уже не считается перегревом. Оператор ищет последнюю запись в опасной части отсортированного журнала.

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

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

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

Выведите индекс последнего измерения с температурой строго больше x. Если превышения нет, выведите -1.

Ограничения

0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не возрастают (совпадения разрешены). При n = 0 вторая строка пустая.

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 4. До закрытия шлюза

Экспедиция «МАЯК». Шлюз исследовательской базы закроется в момент x. Компьютер хранит время событий в отсортированном журнале; события с одинаковым временем возможны. Инженеру нужен номер самого позднего события, которое произошло именно до закрытия. Событие с отметкой ровно x уже не подходит.

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

В первой строке находятся n и x — количество записей и момент закрытия. Во второй строке — n временных отметок по неубыванию.

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

Выведите индекс последнего события, произошедшего строго раньше x. Если ни одно событие не успело, выведите -1.

Ограничения

1 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены).

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 3. Подбор аккумулятора

Экспедиция «МАЯК». Для дальнего выхода роботу требуется запас энергии не меньше x. Батареи на складе стоят в порядке неубывания ёмкости, некоторые имеют одинаковую ёмкость. Снабженец хочет взять первую подходящую батарею: так он не потратит более ёмкий запас без необходимости.

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

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

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

Выведите индекс первой батареи, ёмкости которой хватит для выхода. Если такой батареи нет, выведите -1.

Ограничения

0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены). При n = 0 вторая строка пустая.

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 2. Граница безопасной зоны

Экспедиция «МАЯК». Перед запуском капсулы инженеры рассортировали результаты измерения радиационного фона: от самого большого показания к самому маленькому. Равные результаты стоят рядом. Значение не выше x считается безопасным. Диспетчеру нужна первая запись в этом списке, с которой начинаются безопасные показания. Если безопасных показаний нет, запуск пока не разрешён.

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

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

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

Выведите индекс первого измерения, не превышающего x. Если безопасных измерений нет, выведите -1.

Ограничения

0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не возрастают (совпадения разрешены). При n = 0 вторая строка пустая.

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 1. Пропавшая радиограмма

Экспедиция «МАЯК». Диспетчер получил запрос на радиограмму с кодом x. Все радиограммы хранятся в архиве по возрастанию кода, и двух сообщений с одинаковым кодом не бывает. Диспетчеру нужен номер ячейки, в которой хранится нужная радиограмма. Если такой радиограммы никогда не поступало, нужно сообщить об этом.

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

В первой строке записаны целые числа n и x — количество радиограмм и код запроса. Во второй строке — n различных кодов, расположенных в строго возрастающем порядке.

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

Выведите номер ячейки с кодом x (нумерация с 0). Если радиограммы нет, выведите -1.

Ограничения

0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения строго возрастают. При n = 0 вторая строка пустая.

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

В игре нужно собрать древесину для строительства домика. Рядом растут N деревьев. Высота дерева с номером i равна Ai метрам.

Игрок выбирает одну целую неотрицательную высоту среза H для всех деревьев. У каждого дерева выше H срезается верхняя часть. Её длина добавляется к запасу древесины. Деревья высотой не больше H остаются без изменений.

Например, при высоте среза 6 м дерево высотой 10 м даст 4 м древесины, а дерево высотой 5 м не даст древесины.

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

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

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

Во второй строке записаны N целых чисел A1, A2, …, AN — высоты деревьев.

1 ≤ N ≤ 1000; 1 ≤ A_i ≤ 10⁹; 1 ≤ K ≤ A₁ + A₂ + … + A_N.

При высоте среза 0 древесины всегда достаточно.

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

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

Для турнира приготовили N лент. Длина ленты с номером i равна Ai сантиметров.

Из них нужно вырезать не менее K одинаковых ленточек для медалей. Длина каждой полученной ленточки должна быть целым положительным числом сантиметров.

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

Найдите наибольшую возможную длину одной ленточки.

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

В первой строке записаны два целых числа N K — количество исходных лент и необходимое количество ленточек.

Во второй строке записаны N целых чисел A1, A2, …, AN — длины исходных лент.

1 ≤ N ≤ 1000; 1 ≤ A_i ≤ 10⁹; 1 ≤ K ≤ A₁ + A₂ + … + A_N.

Таким образом, ленточек длиной 1 см всегда хватит.

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

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

Для школьного праздника нужно изготовить не менее K игрушек. На фабрике есть N автоматов. Автомат с номером i изготавливает одну игрушку за Ai минут.

Все автоматы начинают работу одновременно в момент времени 0 и работают независимо друг от друга. Закончив игрушку, автомат сразу начинает следующую. Материалов достаточно, готовых игрушек в начале нет.

Игрушка учитывается только после полного завершения работы над ней. Например, автомат, которому нужны 3 минуты, выпускает игрушки в моменты 3, 6, 9 минут и так далее.

Найдите минимальное время, за которое будет готово не менее K игрушек.

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

В первой строке записаны два целых числа N K — количество автоматов и необходимое количество игрушек.

Во второй строке записаны N целых чисел A1, A2, …, AN — время изготовления одной игрушки каждым автоматом.

1 ≤ N ≤ 1000; 1 ≤ K ≤ 10⁹; 1 ≤ A_i ≤ 10⁶.

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

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

К школьной выставке подготовили N одинаковых прямоугольных карточек. Ширина каждой карточки — A сантиметров, высота — B сантиметров.

Карточки нужно разместить на квадратном стенде ровными горизонтальными рядами. В каждом ряду карточки стоят рядом, а ряды располагаются один над другим. Все карточки ориентированы одинаково: сторона A расположена горизонтально, сторона B — вертикально. Поворачивать карточки, накладывать их друг на друга и выпускать за края стенда нельзя. Зазоры между карточками не нужны; часть мест может остаться пустой.

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

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

В одной строке записаны три целых числа A B N.

1 ≤ A, B ≤ 1000; 1 ≤ N ≤ 10⁶.

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

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

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Алекс настраивает связь между исследовательскими станциями. Есть 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 останется.