Бинарный поиск — это быстрый способ что-то найти в упорядоченных данных. Общий принцип такой: пусть есть некоторое множество возможных решений. На каждом шаге будем делить его на две равные части и определять, в какой из частей должен находиться подходящий элемент. На следующем шаге в качестве множества решений берём эту часть и повторяем с ней ту же операцию. Таким образом, на каждом шаге количество возможных решений сокращается в два раза, и в конце концов сократится до 1 — это и будет наше решение (или мы поймём, что решения нет).
Чтобы использовать бинарный поиск, нужно определить левую (left) и правую (right) границы множества возможных решений. А потом найти середину (middle) — элемент, который делит всё множество на две равные части. Для элемента middle следует проверить условие, по которому можно будет определить, с какой стороны от этого элемента находится решение. После проверки условия левая или правая граница сдвигается к середине, и можно переходить к следующему шагу цикла.
Если множество значений — интервал, и решение нужно определить с некоторой точностью, то бинарный поиск позволит на каждом шаге цикла уменьшать этот интервал в два раза. Когда интервал, в котором может находиться решение, уменьшится до заданной точности, то в качестве решения подойдёт любое значение из этого интервала.
A: Бинарный поиск
Требуется реализовать алгоритм бинарного поиска.
В первой строке входных данных содержатся натуральные числа $N$ и $K$ $(0 < N, K \leqslant 100000)$. Во второй строке задаются $N$ элементов первого массива, отсортированного по возрастанию, а в третьей строке — $K$ элементов второго массива. Элементы обоих массивов — целые числа, каждое из которых по модулю не превосходит $10^9$.
Требуется для каждого из $K$ чисел вывести в отдельную строку YES, если это число встречается в первом массиве и NO в противном случае.
Обратите внимание, требуется именно бинарный поиск. Решение с множествами, словарями и т.п. засчитываться не будут.
10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12
NO
NO
YES
YES
NO
IDE
B: Левый и правый бинарный поиск
Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке. Реализуйте для этого две функции: левый и правый бинарный поиск.
В первой строке входных данных записано два числа $N$ и $M$ $(1 \leqslant N,M \leqslant 20000)$. Во второй строке записано $N$ упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны $M$ целых неотрицательных чисел — элементы второго списка.
Программа должна вывести $M$ строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число $0$.
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
10 10
3 4
7 7
1 2
0
IDE
C: Бинарный поиск — подсчёт количества элементов, равных данному числу
Требуется определить в заданном массиве количество элементов, равных искомому числу.
В первой строке вводится количество чисел в массиве — натуральное число $N$, не превосходящее $10^5$.
Во второй строке вводятся $N$ натуральных чисел, не превосходящих $10^9$, каждое следующее не меньше предыдущего.
В третьей строке вводится количество искомых чисел $M$ — натуральное число, не превосходящее $10^6$.
В четвертой строке вводится $M$ натуральных чисел, не превосходящих $10^9$.
Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.
Если в массиве нет такого числа, выведите 0.
В первой строке входных данных содержатся числа $N$ и $K$ $(0 < N,K < 100001)$. Во второй строке задаются $N$ чисел первого массива, отсортированного по неубыванию, а в третьей строке — $K$ чисел второго массива. Каждое число в обоих массивах по модулю не превосходит $2\cdot 10^9$.
Для каждого из $K$ чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
6 6
1 3 5 7 9 15
2 4 8 1 6 13
1
3
7
1
5
15
IDE
E: Вещественный бинарный поиск
Найдите такое число $x$, что $x^2+\sqrt{x}=C$. Найденное значение $x$ должно быть вычислено с точностью не менее $6$ знаков после точки.
В единственной строке содержится вещественное число $C$ $(1.0 \leqslant C \leqslant 10^{10})$.
Выведите одно число — искомый $x$.
2.0000000000
1.000000000
Подсказка
Не понимаю, при чём тут вообще бинарный поиск?
Функция, значение которой нужно сравнивать с $C$, монотонно возрастает. Можно оценить, в каком интепвале следует искать значение $x$, проверить значение функции в середине этого интервала и определить, с какой стороны от середины следует искать значение $x$ на следущем шаге. Таким образом, на каждом шаге интервал возможных значений будет становиться в 2 раза меньше.
Действительных чисел ведь бесконечно много, сколько ни дели пополам, всё равно останется бесконечность...
Нужно найти не точный ответ, а число с заданной точностью. Это значит, что найденное число $x$ может отличаться от точного решения на заданную величину.
То есть мы могли бы разделить интервал возможных значений на отрезочки, равные требуемой точности. Таких отрезков конечное число! И нам на самом деле нужно найти не решение, а отрезок (равный заданной точности), на котором это решение находится. В физике это записывается как величина, измеренная с некоторой погрешностью.
Всё равно не понимаю, когда остановиться, и какое решение будет принято системой?
Системой будет принято любое решение, которое отличается от точного не больше, чем на заданную точность. Как только диапазон решений сузится на эту величину, продолжать поиск не имеет смысла.
IDE
F: Корень кубического уравнения
Дано кубическое уравнение $ax^3+bx^2+cx+d=0$ $(a\ne0)$. Известно, что у этого уравнения ровно один корень. Требуется его найти.
Во входных данных через пробел записаны четыре целых числа: $-1000 \leqslant a,b,c,d \leqslant 1000$.
Выведите единственный корень уравнения с точностью не менее $4$ знаков после десятичной точки.
1 -3 3 -1
0.999999598818135
Подсказка
Не понимаю, как вообще решать эту задачу?
Точно так же, как предыдущую.
Я не знаю, как ведёт себя функция из задачи. А вдруг она не монотонна?
В общем случае кубический многочлен действительно не является монотонной функцией. Но в данной задаче это не важно, поскольку известно, что корень всего один. Это значит, что с одной стороны от корня значение строго больше 0, а с другой — строго меньше (от чего зависит, с какой именно стороны значение больше 0?)
Перед тем, как применять бинарный поиск, следует привести уравнение к такому виду, чтобы, например, справа от корня функция была положительна, а слева — отрицательна. Подумайте, как это сделать, чтобы корни уравнения не изменились.
Не понимаю, в каких границах следует искать корень?
Заметьте, что коэффициенты при степенях $x$ отличаются по модулю не больше, чем в 1000 раз. Какой, например, корень может получиться, если взять максимальное отношение между $b$ и $a$? Может ли быть у этого уравнения корень в несколько раз больше?
IDE
G: Ксерокопии
Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще $N$ копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за $x$ секунд, а другой — за $y$. Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.
Помогите ему выяснить, какое минимальное время для этого потребуется.
На вход программы поступают три натуральных числа $N$, $x$ и $y$, разделенные пробелом ($1 \leqslant N \leqslant 2\cdot10^8, 1 \leqslant x, y \leqslant 10$).
Выведите одно число — минимальное время в секундах, необходимое для получения $N$ копий.
4 1 1
3
5 1 2
4
IDE
H: Дипломы
Вычислить наименьшую сторону квадрата, в который можно уложить без наложений $N$ одинаковых прямоугольников данного размера. Стороны прямоугольников параллельны сторонам квадрата, поворачивать прямоугольники нельзя.
Входной файл содержит три целых числа: $w,h,N$ $(1 \leqslant w,h,n \leqslant 10^9)$ — ширина и высота прямоугольника и их количество.
В выходной файл необходимо вывести ответ на поставленную задачу — длину стороны квадрата.
2 3 10
9
1 1 1
1
IDE
I: Провода
Дано $N$ отрезков провода длиной $L_1, L_2, \ldots, L_N$ сантиметров.
Требуется с помощью разрезания получить из них $K$ равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить $K$ отрезков длиной даже $1$ см, вывести $0$.
В первой строке находятся числа $N$ и $K$ $(1 \leqslant N \leqslant 10000, 1 \leqslant K \leqslant 10000)$. В следующих $N$ строках — $L_1,L_2,\ldots,L_N$ $(100 \leqslant L_i \leqslant 10^7)$, все числа целые, по одному числу в строке.
Требуется вывести одно число — полученную длину отрезков.
4 11
802
743
457
539
200
5 7
39
39
39
39
39
19
3 1
5
10
15
15
IDE
J: Коровы — в стойла!
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.
В первой строке вводятся числа $N$ $(2 < N < 10001)$ — количество стойл и $K$ $(1 < K < N)$ — количество коров. Во второй строке задаются $N$ натуральных чисел в порядке возрастания — координаты стойл (координаты не превосходят $10^9$).
Выведите одно число — наибольшее возможное допустимое расстояние.
6 3
2 5 7 11 15 20
9
IDE
K: Билеты
В одной театральной кассе есть в продаже билеты любой стоимости, выражающейся натуральным числом. При покупке билетов по цене за билет от $A$ до $B$ рублей включительно нужно дополнительно оплатить сервисный сбор в размере $C$ процентов от номинальной стоимости билетов (сервисный сбор не обязательно выражается целым числом рублей, но всегда выражается целым числом копеек). При покупке билетов стоимостью менее $A$ рублей за билет, а также более $B$ рублей за билет, сервисный сбор не берется.
У вас есть $X$ рублей и вам нужно $K$ билетов одинаковой цены (цена обязательно должна выражаться натуральным числом рублей, $0$ не считается натуральным). Билеты какого самого дорогого номинала вы можете себе позволить?
Вводятся целые $A,B,C,X,K$ $(1 \leqslant A \leqslant B \leqslant 10^9,0 \leqslant C \leqslant 1000,0 \leqslant X \leqslant 10^9,1 \leqslant K \leqslant 100000)$.
Если на имеющиеся деньги невозможно приобрести ни одного билета, выведите 0. Иначе выведите натуральное число — номинальную стоимость приобретённых билетов.
1 10 0 5 5
1
10 100 50 50 5
9
10 100 50 100 5
13
IDE
L: Лифт
Высокое здание, состоящее из $N$ этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от $1$ до $N$ снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для $i$-го этажа эта величина равна $A_i$. Известно, что лифт не может перевозить более $C$ человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно, вверх или вниз) ему требуется $P$ секунд. Какое наибольшее количество человек лифт может перевезти на парковку за $T$ секунд, если изначально он находится на уровне парковки?
В первой строке входного файла содержатся целые числа $N,C,P,T$. Вторая строка содержит последовательность $N$ целых чисел $A_1,A_2,\ldots,A_N$.
Ограничения: $1 \leqslant N \leqslant 100,1 \leqslant C \leqslant 10^9,1 \leqslant P \leqslant 10^9,1 \leqslant T \leqslant 10^9, 0 \leqslant A_i \leqslant 10^9$. Сумма всех значений последовательности не превосходит $10^9$.
Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.
4 5 2 15
0 1 2 3
3
4 5 2 18
0 1 2 3
5
3 2 1 9
1 1 1
3
IDE
M: Шарики на детском празднике
Организаторы детского праздника планируют надуть для него $M$ воздушных шариков. С этой целью они пригласили $N$ добровольных помощников, $i$-й среди которых надувает шарик за $T_i$ минут, однако каждый раз после надувания $Z_i$ шариков устаёт и отдыхает $Y_i$ минут.
Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придётся, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха.
В первой строке входных данных задаются числа $M$ и $N$ $(0 \leqslant M \leqslant 15000,1 \leqslant N \leqslant 1000)$. Следующие $N$ строк содержат по три целых числа — $T_i,Z_i$ и $Y_i$ соответственно $(1 \leqslant T_i,Y_i \leqslant 100,1 \leqslant Z_i \leqslant 1000)$.
Выведите в первой строке число $T$ — время, за которое будут надуты все шарики. Во второй строке выведите $N$ чисел — количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
2 2
1 1 1
1 1 1
1
1 1
3 2
2 2 5
1 1 10
4
2 1
IDE
N: Дремучий лес (задача на тернарный поиск максимума/минимума унимодальной функции)
Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.
Судиславль находится в точке с координатами $(0,1)$.
«Берендеевы поляны» находятся в точке с координатами $(1,0)$.
Граница между лесом и полем — горизонтальная прямая $y=a$, где $a$ — некоторое число $(0 \leqslant a \leqslant 1)$.
Скорость передвижения СЭС по полю составляет $V_p$, скорость передвижения по лесу — $V_f$. Вдоль границы можно двигаться как по лесу, так и по полю.
Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.
В первой строке входного файла содержатся два положительных целых числа $V_p$ и $V_f$ $(1 \leqslant V_p,V_f \leqslant 10^5)$. Во второй строке содержится единственное вещественное число — координата по оси $Oy$ границы между лесом и полем $a$ $(0 \leqslant a \leqslant 1)$.
В единственной строке выходного файла выведите вещественное число с точностью не менее $8$ знаков после запятой — координата по оси $Ox$ точки, в которой инспекция СЭС должна войти в лес.
5 3
0.4
0.783310604
5 5
0.5
0.500000000
Подсказка
Какое страшное название! Наверное, это очень сложная задача...
Унимодальная функция — функция, имеющая на заданном отрезке ровно один минимум или максимум. Именно такой является функция зависимости времени от координаты $x$ входа в лес.
Тернарный поиск означает, что вместо деления отрезка на две части, как в бинарном поиске, придётся делить его на три части. А вот как с помощью деления отрезка на 3 части найти единственный минимум функции, попробуйте придумать сами (это не так уж сложно!)
