Бинарный поиск по ответу

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

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

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

Первая строка входных данных содержит  количество домов на улице N и количество театров K (1 ≤ K ≤ N ≤ 104). Далее идет N чисел в порядке возрастания  – координаты домов на улице.

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

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

N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше R). Взрывать бомбу можно только в целые моменты времени.

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

Входные данные
В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках  содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 10⁵. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.

Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.

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

Если решений несколько, выведите любое из них.

Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложение своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.

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

Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север - юг и восток - запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север - юг и восток - запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север - юг и восток - запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный - координаты (W, H), где W и H - длина и ширина парка соответственно.

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



Входные данные
Первая строка содержит три целых числа, N, W и H, разделённых пробелами: N - число деревьев в парке, W и H - длина и ширина парка соответственно.

Следующие N строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа xi и yi, разделённых пробелом и представляющих собой координаты i-го дерева. Все деревья имеют различные координаты.

Ограничения: 1 <= N <= 100, 1 <= W, H <= 10 000, 0 <= x_i <= W, 0 <= y_i <= H.

Выходные данные
Вывести через пробел три целых числа, P, Q и L, где (P, Q) - координаты юго-западного угла поля для крикета, L - длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером X×Y метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось N круглых колонн, снести которые не представляется возможным.

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

Входные данные
В первой строке входных данных содержатся вещественные числа X и Y, 1 <= X, Y <= 10⁴ . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (X, 0), (X, Y) и (0, Y).

Во второй строке задается число N (0 <= N <= 10) - количество колонн. Следующие N строк содержат параметры колонн - i-я строка содержит три вещественных числа X_i, Y_i и R_i - координаты центра и радиус i-й колонны (R_i <= X_i <= X-R_i, R_i <= Y_i <= Y-R_i, 0.1 <= R_i <= min(X / 2, Y / 2); для любых i ≠ j sqrt( (X_i - X_j)2 + (Y_i - Y_j)2 )>= R_i + Rj). Все вводимые числа разделены пробелами.

Выходные данные
Выведите три вещественных числа: X_F, Y_F и R_F - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.

Сегодня день рождения Никиты. На празднование дня рождения приглашены n детей (включая самого Никиту). Все дети пронумерованы числами от 1 до n. Работники МакДональдса приготовили большой круглый стол и поставили вокруг него n стульев.

Как только дети приходят на день рождения, они рассаживаются за столом. Ребенок с номером 1 занимает одно из мест. Ребенок с номером 2 занимает место слева от ребенка с номером 1. Ребенок с номером 3 занимает следующее за ним место слева и так далее. Наконец, ребенок с номером n
 займет оставшееся свободное место между детьми с номерами n – 1 и 1.

Работники МакДональдса хорошо знают, что некоторые из приглашенных детей ведут себя весьма шумно за столом, если сидят друг с другом. Поэтому работники ресторана собираются пересадить детей в некотором порядке. Этот порядок описывается перестановкой p₁, p₁,..., p_n (p₁, p₂,..., p_n — различные целые числа от 1 до n). То есть, ребенок p₁ должен сидеть между p_n и p₂, ребенок p_i (i = 2, 3, ... , n − 1) должен сидеть между p_i-1 и p_i+1; ребенок p_n должен сидеть между p_n-1 и p1.

К сожалению, все дети пришли и расселись так, как указано в первом абзаце. Поэтому для того, чтобы рассадить детей в нужном порядке, придется пересадить кого-то из детей на некоторое количество мест влево или вправо. Для каждого ребенка работникам ресторана необходимо решить, как он будет пересаживаться: они должны выбрать направление (влево или вправо) и расстояние (на сколько мест нужно переместиться). Затем, по заданному сигналу все дети должны одновременно встать и переместиться на места, определенные работниками МакДональдса.

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

Имейте в виду, что ребенок p_i может сидеть как слева, так и справа от ребенка pn.

Задание
Ваша задача — написать программу, которая:
· читает из стандартного ввода количество детей и перестановку, определяющую желаемый порядок рассадки детей,
· вычисляет минимально возможную величину беспорядка,
· выводит результат в стандартный вывод.

Входные данные
В первой строке стандартного ввода содержится единственное целое число n (1 ≤ n ≤ 1 000 000). Во второй строке содержатся n целых чисел p₁, p₂,..., p_n, разделенных одним пробелом. Числа p₁, p₂,..., p_n образуют перестановку множества {1, 2, ... , n}, описывающую желаемый порядок рассадки детей. Кроме того, в 50% тестов число n не будет превышать 1 000.

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

Пояснения

На рисунке слева изображена исходная рассадка детей. На рисунке в середине показан результат пересаживания, при котором дети с номерами 1 и 2 перемещаются на одно место, дети с номерами 3 и 5 перемещаются на два места и дети с номерами 4 и 6 не меняют своего положения. Требуемые условия рассадки выполнены, поскольку 3-й сидит между 6-м и 4-м, 4-й сидит между 3-м и 5-м, 5-й сидит между 4-м и 1-м, 1-й сидит между 5-м и 2-м, 2-й сидит между 1-м и 6-м и 6-й сидит между 2-м и 3-м. Также существует другой вариант конечной рассадки детей, изображенный на рисунке справа. В обоих вариантах величина беспорядка равна 2.

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

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

Сад представляет собой прямоугольник длиной l метров и шириной w метров, который разделен на l·w одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (x,y), удовлетворяющие ограничениям 1 <= x <= l, 1 <= y <= w. В каждом единичном квадрате может содержаться любое количество роз.

Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (l₁,w₁), (l₁ ,w₂), (l₂, w₁) и (l₂,w₂) (для 1 <= l₁ <= l₂ <= l и 1 <= w₁ <= w₂ <= w):

• содержит все единичные квадраты с координатами (x,y), которые удовлетворяют условию l₁ <= x <= l₂ и w₁ <= y <= w2, и
• имеет периметр 2 · (l₂−l₁+1)+ 2 · (w₂−w₁+1).

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

Задание
Напишите программу, которая:

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

Входные данные
Первая строка стандартного ввода содержит два числа: l и w (1 <= l, w <= 250), разделенных одним пробелом – длину и ширину сада. Во второй строке задаются два числа: n и k (2 <= n <= 5000, 1 <= k <= n/2), записанных через пробел и обозначающих общее количество роз в саду и количество роз, которое должно быть в каждой из прямоугольных областей. Следующие n строк содержат позиции роз, по одной розе в строке. Каждая (i+2)-я строка содержит два числа l_i, w_i (1 <= l_i <= l, 1 <= w_i <= w), разделенных одним пробелом – координаты квадрата, содержащего i-ю розу.

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

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

Рисунок к тесту:

В столице одной Очень Демократической Страны все жители в 8 часов утра одновременно выходят со станций метро, ближайших к месту своей работы, и дальше добираются до работы на автобусах. Мэр города хочет построить еще одну станцию метро так, чтобы после этого время, к которому все люди доберутся до места своей работы (то есть время, когда последний работник окажется на работе), было наименьшим возможным.

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

Входные данные
В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

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

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

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

В одном королевстве есть \(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\).

На числовой оси, в промежутке от L до R, Василий нарисовал N вертикальных палочек. Подумав, Василий решил, что ему на числовой оси необходим пустой промежуток шириной не менее W.
Помогите определить Василию, какое минимальное количество палочек необходимо стереть Василию и какие именно.
После того как Василий сотрет некоторое количество палочек, должен найтись промежуток шириной больше или равной W. Промежуток может располагаться между двумя оставшимися палочками, или между оставшейся палочкой и концом промежутка числовой оси, или между двумя концами промежутка числовой оси.

Входные данные
Первая строка содержит два целых числа N и W — количество нарисованных палочек и минимально необходимую ширину промежутка соответственно. Гарантируется, что 0 <= N <= 1 000 000 и 0 <= W <= 1 000 000.
Во второй строке находятся два числа L и R — координаты левого и правого конца промежутка числовой оси (L <= R). В третьей строке записаны N чисел — координаты нарисованных палочек. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 1 000 000. Гарантируется, что все палочки нарисованы между левым и правым концами стороны.


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

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите одну строку, содержащую число  - 1.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 2 6 3 4 5	1 1
2	3 2 1 6 4 3 5	0
3	3 5 1 7 5 3 4	3 2 3 1