На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.
В первой строке вводятся числа \(N\) \((2 \lt N \lt 10001)\) – количество стойл и \(K\) (\(1 \lt K \lt N )\) – количество коров. Во второй строке задаются \(N\) натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят \(10^9\))
Выведите одно число – наибольшее возможное допустимое расстояние.
6 3 2 5 7 11 15 20
9
Реализуйте алгоритм приближенного бинарного поиска.
В первой строке входных данных содержатся числа \(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
1 3 7 1 5
Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
Вводится одно число N
Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.
5
3
Реализуйте алгоритм бинарного поиска.
В первой строке входных данных содержатся натуральные числа \(N\) и \(K\) (\(0 \lt N, K \le 100\,000\)). Во второй строке задаются \(N\) элементов первого массива, отсортированного по возрастанию, а в третьей строке – \(K\) элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109
Требуется для каждого из 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
В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено ai саженцев.
Для достижения эстетического совершенства высаживаемого ряда деревьев требуется, чтобы среди любых P подряд идущих деревьев все деревья были разных видов. Если количество деревьев в ряду меньше P, то все они должны быть различны.
Требуется написать программу, которая находит максимальное количество деревьев в эстетически совершенном ряду, посаженном из закупленных саженцев.
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида (1 ≤ ai ≤ 109), по одному числу в каждой строке.
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.
3 3 1 200 1
4