#2

Темы: [Бинарный поиск в массиве]

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

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

В первой строке входных данных содержатся числа \(N\) и \(K\) (\(0 \lt N,\,K \lt 100\,001\)). Во второй строке задаются \(N\) чисел первого массива, отсортированного по неубыванию, а в третьей строке – \(K\) чисел второго массива. Каждое число в обоих массивах по модулю не превосходит \(2\cdot10^9\).

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

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

Примеры

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

5 5
1 3 5 7 9 
2 4 8 1 6

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

#3

Сложность двоичного поиска

Темы: [Бинарный поиск в массиве]

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

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

Вводится одно число N

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

Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.

Примеры

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

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

#4

Двоичный поиск

Темы: [Бинарный поиск в массиве]

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

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

В первой строке входных данных содержатся натуральные числа \(N\) и \(K\) (\(0 \lt N, K \le 100\,000\)). Во второй строке задаются \(N\) элементов первого массива, отсортированного по возрастанию, а в третьей строке – \(K\) элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 10⁹

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

Требуется для каждого из 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

#23

То березка, то рябина…

Темы: [Бинарный поиск по ответу] [Бинарный поиск в массиве] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2007, 2 день, Задача A ]

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

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

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

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

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

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

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

Примеры

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

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

#406

Выборы

Темы: [Бинарный поиск в массиве] [Быстрая сортировка] [Бинарный поиск по ответу]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача D ]

Задана информация об N партиях - количестве голосующих за них и размер взятки, который необходимо дать партии, чтобы она делала что нужно, если победит. Изменение результата голосования одного человека стоит 1 уе. Требуется за наименьшее количество денег подкупить партию и людей так, чтобы она победила.

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

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

Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того, чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы i-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере p_i условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.

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

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

В первой строке вводится целое число n – количество партий ( 1<= n <=10⁵). Следующие n строк описывают партии. Каждая из этих строк содержит по два целых числа: v_i – количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и p_i – взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена ( 1<=v_i<=10⁶, 1<=p_i<=10⁶ или p_i = - 1). Если партия является идеологически устойчивой, то p_i равно -1. Гарантируется, что хотя бы одно p_i не равно -1.

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

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

Примеры

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

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

6
3
3 2 5