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

Маяк 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\) различных целых чисел: \(A = [a_1, a_2, \ldots, a_n]\) и \(B = [b_1, b_2, \ldots, b_n]\).

Составим из них \(n^2\) дробей вида \(a_i / b_j\), сократим каждую дробь и отсортируем их по неубыванию.

Задано число \(q\) и \(q\) целых чисел \(c_1, c_2, \ldots, c_q\). Для каждого \(j\) следует выдать \(c_j\)-ю в неубывающем порядке дробь из получившихся.

Формат входных данных
На первой строке ввода находятся числа \(n\) и \(q\) (\(1 \le n \le 10^5\), \(1 \le q \le 10^5\), \(q \le n^2\)).

Дополнительно выполняется неравенство \(n\cdot q \le 10^5\).

На второй строке ввода находятся \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)).

На третьей строке ввода находятся \(n\) различных целых чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le 10^6\)).

На четвертой строке ввода находятся \(q\) различных целых чисел \(c_1, c_2, \ldots, c_q\) (\(1 \le c_i \le n^2\)).

Формат выходных данных
Выведите \(q\) строк. На \(j\)-й строке выведите \(c_j\)-ю по неубыванию дробь среди получившихся. Дробь \(p/q\) следует выводить в формате <<p q>>, дробь должна быть несократимой.

Замечание
В примере дроби исходно равны: \[\left[ \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \frac{3}{5}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \frac{2}{5} \right],\] после сокращения \[\left[ \frac{3}{2}, \frac{1}{1}, \frac{3}{4}, \frac{3}{5}, \frac{2}{1}, \frac{4}{3}, \frac{1}{1}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{1}, \frac{2}{3}, \frac{1}{2}, \frac{2}{5} \right],\] после сортировки \[\left[ \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{2}{1} \right].\]

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

Входные данные
В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

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

Примеры

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

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге ai страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

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

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·10⁵) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a1, a2, ... an (1 <= a1<= 10¹⁰), где ai равно количеству страниц в i-й книге. В третьей строке следует последовательность d1, d2, ... dm (1 <= dj <= a1 + a2 +...+ an), где dj равно общему числу страниц, прочитанных Томми к j-му дню. Все dj заданы в порядке возрастания.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= ak), на которой остановился Томми в текущий день.

 

Примеры

№	Входные данные	Выходные данные
1	3 6 10 15 12 1 9 12 13 15 17	1 1 1 9 2 2 2 3 2 5 2 7
2	2 3 5 10000000000 5 6 9999999999	1 5 2 1 2 9999999994

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

Для достижения эстетического совершенства высаживаемого ряда деревьев требуется, чтобы среди любых P подряд идущих деревьев все деревья были разных видов. Если количество деревьев в ряду меньше P, то все они должны быть различны.

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

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

 

Примеры

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

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

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.