Бинарный поиск

Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему <<Умный дом>>. В соответствующую программу Максим заложил два целых числа \(t_{min} \leq t_{max}\) и следующий алгоритм использования обогревателя:

1. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше \(t_{min}\), то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.

2. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше \(t_{max}\), то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения \(t_{min}\) и \(t_{max}\) Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из \(n\) дней использования системы.

Максим помнит, что \(t_{min}\) и \(t_{max}\) были целыми числами, по модулю не превосходящими \(10^9\) и \(t_{min} \leq t_{max}\), также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал \(t_{min}\) и \(t_{max}\) как можно более близкими друг к другу.

Помогите найти два подходящих значения \(t_{min}\) и \(t_{max}\), не превосходящих \(10^9\) по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из \(n\) дней, \(t_{min}\) не превосходит \(t_{max}\) и величина \(t_{max} - t_{min}\) минимальна.

Гарантируется, что записи программы правильные, и такие два числа существуют.

Формат входных данных
В первой строке задано целое число \(n\) (\(5 \leq n \leq 10^5\)) — количество дней, в течение которых работала система.

Во второй строке входных данных задаются \(n\) целых чисел \(t_1, \dots, t_n\) (\(-10^9 \leq t_i \leq 10^9\)) — температуры на улице в каждый из \(n\) дней.

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

Формат выходных данных
В единственной строке выведите два целых числа \(t_{min}\) и \(t_{max}\) (\(t_{min} \leq t_{max}\)), по модулю не превосходящих \(10^9\) — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение \(t_{max} - t_{min}\) минимально.

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

В первом тестовом примере первые пять дней температура строго меньше \(7\) градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию \(6 \leq t_{min} = t_{max} \leq 10^9\).

На доске выписано две последовательности из \(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].\]

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

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

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

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

 

После тяжелого контеста бывает полезно выпить немного кофе. У настоящих программистов есть множество различных сортов кофе, которые постепенно добавляются в одну кружку. При этом мы будем рассматривать кофе с определенной особенностью: разные сорта кофе держатся в кружке <<слоями>> и не перемешиваются.

Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито \(n\) сортов, \(i\)-й сорт характеризуется уровнем крепости \(p_i\) и высотой слоя, который он занимает в кружке, \(h_i\). При этом если \(i < j\), то слой кофе \(i\)-го сорта находится ниже кофе \(j\)-го сорта. Также известно, что высота кружки равна \(\sum\limits_{i=1}^n h_i\), то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.

Для разнообразия иногда хочется получить из такого <<коктейля>> напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как \[P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}\]

Чтобы как-то изменять \(P\), можно

1. выбрать трубочку произвольной высоты \(h\);

2. один или более раз выполнить следующее: погрузить ее в напиток на любую глубину от \(0\) до \(h\) включительно относительно верхнего края кружки (не относительно текущего уровня жидкости) и отпить произвольное (не обязательно целое) количество кофе с того уровня, на который попал нижний конец трубочки.

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

Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости \(t_i\), и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка \(t_i\).

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(q\) — количество слоев кофе в кружке и количество запросов (\(1 \le n, q \le 2 \cdot 10^5\)).

Следующие \(n\) строк содержат по два целых числа \(p_i\) и \(h_i\) — уровень крепости и высоту \(i\)-го снизу кружки слоя кофе (\(1 \le p_i, h_i \le 10^9\)). Гарантируется, что сумма \(p_i \cdot h_i\) по всем \(i\) не превосходит \(10^{18}\).

В \(i\)-й из следующих \(q\) строк дано единственное целое число \(t_i\), определяющее \(i\)-й запрос (\(1 \le t_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых содержится единственное целое число от \(0\) до \(n\) — ответ \(i\)-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число \(-1\).

 

Замечание
Для примера из условия:

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

2. Во втором запросе достаточно выпить часть кофе со второго сверху слоя.

3. В третьем запросе понадобится выпить первый и третий слой кофе.

4. В четвертом запросе невозможно добиться уровня крепости \(4\).

В одном королевстве есть \(n\) городов, расположенных вдоль длинной прямой дороги, \(i\)-й город расположен на расстоянии \(x_i\) километров от начала дороги (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

В ближайшее время король планирует провести реформу управления королевством и разделить его на \(k\) провинций. Каждый город должен войти ровно в одну провинцию.

В каждую провинцию войдет от \(a\) до \(b\) городов, причем эти города должны иметь следующие подряд номера. Таким образом, каждая провинция характеризуется числами \(i\) и \(l\), для которых \(1 \le i\), \(i + l - 1 \le n\), \(a \le l \le b\) и в провинцию входят города с номерами \(i, i + 1, \ldots, i + l - 1\).

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

Формат входных данных
Первая строка ввода содержит четыре целых числа: \(n\), \(k\), \(a\) и \(b\) (\(1 \le n \le 200\), \(1 \le k \le n\), \(1 \le a \le b \le n\), \(ak \le n \le bk\)). Вторая строка ввода содержит \(n\) целых чисел: \(x_1, x_2, \ldots, x_n\) (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

Формат выходных данных
Выведите одно целое число: минимальное возможное \(z\), такое чтобы можно было разбить города на провинции описанным образом, и расстояние между городами внутри одной провинции не превышало \(z\).

Примечание
В примере оптимально первые 4 города объединить в первую провинцию, а пятый и шестой — во вторую. Максимальное расстояние между двумя городами в одной провинции: \(13 - 6 = 7\).

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует \(n\) видов цветов, занумерованных от 1 до \(n\). Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть \(a_i\) штук цветов вида \(i\). На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

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

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Мэр Цветочного города попросил лучшего плиточника Тайлера замостить квадратную зону площади плиткой. Тайлеру были выданы коробки, в каждой из которых содержится ai квадратных плиток размером 1х1. Тайлеру поставили условие, что он должен обязательно использовать все плитки, которые ему были выданы. 
Помогите Тайлеру определить, сможет ли он использовать все плитки, чтобы замостить из всех них квадрат какого-либо размера или ему придется идти к мэру и просить еще плиток?
Считайте, что на площади можно замостить квадрат любого размера. 

Формат входных данных
В первой строке вводится натуральное число n (1 ≤ n ≤ 2·105)- количество коробок, выданных Тайлеру. Во второй строке записаны n чисел ai (1 ≤ ai ≤ 109)- количество плиток в i-й коробке.

Формат выходных данных
Выведите YES, если Тайлер сможет из всех плиток замостить квадрат какого-либо размера на площади, в противном случае выведите NO.

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



Решите задачу двоичным поиском.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 231 - 1) - количество блоков.

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

Для заданного целого положительного числа num, выведите 1, если num является полным квадратом, или 0 в противном случае.
Полный квадрат - это целое число, которое является квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.

Решите задачу с помощью бинарного поиска.


Формат входных данных
Программа получает на вход одно целое положительное число num (1 <= num <= 231 - 1).

Формат выходных данных
Выведите 1, если num является полным квадратом, или 0 в противном случае

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия резила плохой (возвращает True, если версия плохая, и False если хорошая).

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

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия релиза плохой (возвращает True, если версия плохая, и False если хорошая).

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

Ваша функция должна вернуть номер первого плохого релиза.
 

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

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

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

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

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

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