Бинарный поиск в массиве

Маяк 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 начинается в момент 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. Окончание первого совпадает с началом второго; можно посетить оба.

Алекс выбирает мастер-классы научного фестиваля. Мастер-класс 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. Из трёх совместимых мастер-классов нужно выбрать два: второй и третий.

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

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

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

Для каждого запроса выведите ответ на отдельной строке.

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤100).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 30000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

Дано 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 — количество слов в словаре (0≤N≤20000).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

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

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤ 10⁵) – количество элементов в первом массиве. Далее идет N целых чисел, не превосходящих по модулю 10⁹ – элементы первого массива, Далее идет количество элементов M во втором массиве и M элементов второго массива с такими же ограничениями.

Выходные данные
Выведите M чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего или равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.