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

Требуется реализовать алгоритм бинарного поиска.

В первой строке входных данных содержатся натуральные числа $N$ и $K$ $(0 < N, K \leqslant 100000)$. Во второй строке задаются $N$ элементов первого массива, отсортированного по возрастанию, а в третьей строке — $K$ элементов второго массива. Элементы обоих массивов — целые числа, каждое из которых по модулю не превосходит $10^9$.

Требуется для каждого из $K$ чисел вывести в отдельную строку YES, если это число встречается в первом массиве и NO в противном случае.

Обратите внимание, требуется именно бинарный поиск. Решение с множествами, словарями, map'ами, set'ами и т.п. засчитываться не будут.

10 5
1 2 3 4 5 6 7 8 9 10
 -2 0 4 9 12

NO
NO
YES
YES
NO

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

C: Бинарный поиск — подсчёт количества элементов, равных данному числу

Требуется определить в заданном массиве количество элементов, равных искомому числу.
В первой строке вводится количество чисел в массиве — натуральное число $N$, не превосходящее $10^5$.
Во второй строке вводятся $N$ натуральных чисел, не превосходящих $10^9$, каждое следующее не меньше предыдущего.
В третьей строке вводится количество искомых чисел $M$ — натуральное число, не превосходящее $10^6$.
В четвертой строке вводится $M$ натуральных чисел, не превосходящих $10^9$.

Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.
Если в массиве нет такого числа, выведите 0.

4
1 2 2 4
4
1 4 3 2

1
1
0
2

D: Приближённый бинарный поиск

Реализуйте алгоритм приближенного бинарного поиска.

В первой строке входных данных содержатся числа $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

E: Вещественный бинарный поиск

Найдите такое число $x$, что $x^2+\sqrt{x}=C$. Найденное значение $x$ должно быть вычислено с точностью не менее $6$ знаков после точки.

В единственной строке содержится вещественное число $C$ $(1.0 \leqslant C \leqslant 10^{10})$.

Выведите одно число — искомый $x$.

2.0000000000

1.000000000

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

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

H: Дипломы

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

Входной файл содержит три целых числа: $w,h,N$ $(1 \leqslant w,h,n \leqslant 10^9)$ — ширина и высота прямоугольника и их количество.

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

2 3 10

9

1 1 1

1

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

J: Коровы — в стойла!

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

В первой строке вводятся числа $N$ $(2 < N < 10001)$ — количество стойл и $K$ $(1 < K < N)$ — количество коров. Во второй строке задаются $N$ натуральных чисел в порядке возрастания — координаты стойл (координаты не превосходят $10^9$).

Выведите одно число — наибольшее возможное допустимое расстояние.

6 3
2 5 7 11 15 20

9

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

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

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

N: Дремучий лес (задача на тернарный поиск максимума/минимума унимодальной функции)

Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.

1. Судиславль находится в точке с координатами $(0,1)$.
2. «Берендеевы поляны» находятся в точке с координатами $(1,0)$.
3. Граница между лесом и полем — горизонтальная прямая $y=a$, где $a$ — некоторое число $(0 \leqslant a \leqslant 1)$.
4. Скорость передвижения СЭС по полю составляет $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