Алгоритмы поиска

Наиболее известная игра, дошедшая до нас из Японии – это Судоку. Новая игра должна затмить ее славу. Про нее известно следующее. Нам дан квадрат, разделенный сеткой на n×n клеток, а каждая клетка содержит картинку одного из k типов. Игрок должен переместить их, чтобы получить максимально возможное число одинаковых первых рядов (два ряда считаются одинаковыми, если оба заполнены одинаковыми картинками и в одинаковом порядке). По виду таблицы определите, сколько одинаковых рядов в ней можно сложить (если менять картинки как угодно).

Например, если нам дана такая таблица:

одно из результирующих состояний в игре будет:

Входные данные
Первая строка входных данных содержит два числа n (1≤n≤40000) и k (1≤k≤50000). Каждая из следующих k строк содержит число картинок в таблице каждого из k типов. Все числа больше 0, их сумма в точности равна n².

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

Даша имеет n ювелирных украшений. Каждое украшение имеет стоимость wi и значимость для Даши vi. В связи с финансовым кризисом Даша решила продать некоторые украшения и сохранить только k из имеющихся. Чтобы решить, что именно сохранить, Даша вводит параметр важности для набора из выбранных k украшений, который вычисляет по следующей формуле:
\(\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}\)

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

Входные данные
Первая строка ввода содержит числа n – количество ювелирных изделий у Даши и k – количество ювелирных изделий, которые планируется оставить (1 ≤ k ≤ n ≤ 100000).

В следующих n строках содержатся по два числа – v_i и w_i (0 ≤ v_i ≤ 10⁶,1≤w_i≤10⁶, обе суммы всех значений vi и wi не превосходят 10⁷ каждая).

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

Пусть A — массив, состоящий из N элементов A₁,...,A_N. Обозначим его максимальноеи минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S=A₁+A₂+…+A_N. Заменим каждый элемент массива на разницу S и этого элемента: A_i:=S-A_i, 1≤i≤N. Такое преобразование массива A назовем операцией Confuse. Напишите программу, которая по массиву B, полученному в результате K–кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).

Входные данные
Первая строка входного файла содержит целые числа N и K, где N — количество элементов массива B (2 ≤ N ≤ 10000), а K — количество применений операции Confuse к начальному массиву A, 1 ≤ K ≤ 100. Вторая строка файла содержит N элементов массива B. Элементы массива B — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

Выходные данные
Единственная строка выходного файла должна содержать целое число - разность max(A) и min(A).

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

Вот и сейчас ему поручили проверить два стоящих на расстоянии d друг от друга столба высоты h₁ и h₂ соответственно. Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.

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

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

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



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

Входные данные
Входной файл содержит четыре положительных целых числа: d, h₁, h₂ и l - расстояние между столбами, высоту первого и второго столбов и максимальный допустимый перепад высот при прыжке, соответственно. Все числа во входном файле не превышают 10⁶.

Выходные данные
Выведите ответ с максимальной возможной точностью. Ответ будет проверяться с точностью до 10⁻⁵.

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤20000).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

В связи с увеличившимся количеством аварий на железной дороге, руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T₁ минуту поезд идет со скоростью V₁ метр в минуту, потом T₂ минуты со скоростью V₂ метра в минуту, ..., наконец, T_N минут со скоростью V_N метрв в минуту. При этом на любом из этих участков поезд может стоять (V_i = 0).

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

Входные данные
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел T_i и V_i (1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000).

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

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

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

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

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

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

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

Знаменитый театральный критик переезжает в Нью-Йорк. Как известно, все театры в Нью-Йорке размещены на Бродвее, поэтому критик тоже, несомненно, поселится на Бродвее, чтобы быть как можно ближе ко всем театрам. Определите номер дома, в котором должен поселиться критик, чтобы суммарное расстояние от его дома до всех театров было бы минимально. Бродвей представляет собой прямую улицу, на котором подряд, на равном расстоянии друг от друга размещены дома, нумерация которых начинается с 1. В одном доме может находиться несколько театров, критик может поселиться в любом доме, даже если в этом доме находится театр.

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤10⁵)  – количество театров на Бродвее. Далее идет N натуральных чисел, не превосходящих 10⁹  – номера домов, в которых размещены театры.

Выходные данные
Выведите единственное число  – номер дома, в котором должен поселиться критик.

Примеры

№	Входные данные	Выходные данные
1	2 1 10	5
2	3 1 3 5	3

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 - длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H₁ = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (H_i = (H_i - 1 + H_i + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = H_N) при условии, что ни одна из лампочек не должна лежать на земле (H_i > 0 для 1 <= i <= N).

Ограничения: 3 <= N <= 1000 - целое, 10 <= A <= 1000 - вещественное.

Входные данные
В первой строке находятся два числа, N и A.

Выходные данные
Вывести одно вещественное число B с двумя знаками после запятой.

Будем называть цепочкой слов длины n последовательность слов w₁, w₂, …, w_n, такую, что для всех i от 1 до n – 1 слово w_i является собственным префиксом слова w_i+1.

Слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u. Например, «program» является собственным префиксом слова «programmer».

Задано множество слов S = {s₁, s₂, …, s_m} и последовательность чисел x[1], x[2], …, x[k]. Требуется найти такие числа l и r (l ≤ r), что s_x[l], s_x[l + 1], …, s_x[r – 1], s_x[r] является цепочкой слов, и количество слов в цепочке (число r – l + 1) максимально.

Входные данные
Первая строка входного файла содержит целое число m (1 ≤ m ≤ 250 000). Каждая из следующих m строк содержит по одному слову из множества S.

Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.

Следующая строка содержит число k (1 ≤ k ≤ 250 000). Последняя строка входного файла содержит k чисел — последовательность чисел x[1], x[2], …, x[k] (для всех i выполнено 1 ≤ x[i] ≤ m).

Выходные данные
Выведите в первой строке выходного файла два числа: l и r. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером 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, если таких прямоугольников нет.

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

В некотором царстве, в некотором государстве было N  городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.

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

Нелегкая задача выбрать место для столицы поручена Вам.

Входные данные
В первой строке вводится число N - количество городов (1 <= N <= 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.

Выходные данные
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.

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

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

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

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

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

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

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

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

Степень точки \(A\) относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке \(A\), имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки \(A\) до некоторой точки многоугольника: \(d_{min}\) и \(d_{max}\). Степенью точки относительно данного многоугольника назовем минимум величины \(d_{min}\times d_{max}\) по всем таким лучам.

Военные не справляются с задачей вычисления степени наблюдательного центра относительно полигона и решили подключить к этой задаче вас. Помогите им!

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

Формат входных данных
Первая строка содержит число \(n\) — количество вершин полигона (\(3 \le n \le 100\)). Следующие \(n\) содержат по два вещественных числа — координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают \(1000\) по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.

Формат выходных данных
Выведите одно число — степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на \(10^{-4}\).

На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все n своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке a[1], a[2],...,a[n]. Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами i[1], i[2],..., i[k] покрашены в один цвет, то a[i[1]] < a[i[2]] < ... < a[i[k]]. Петя хочет использовать как можно меньше цветов. Помогите ему!

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

Первая строка входного файла содержит число n - количество кубиков у Пети (1 <= n <= 250000). Затем следует n чисел, разделенных пробелами и/или переводами строки - a[1], a[2], ..., a[n].

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

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

Сеня выбирает себе подарки на новый год. Он знает, что Дед Мороз купит ему ровно два подарка: один якобы от мамы, а другой якобы от папы.

В магазине, где Дед Мороз будет покупать подарки, продаётся \(n\) подарков, про каждый подарок известна его цена: цена \(i\)-го подарка равна \(a_i\) рублей. Сеня знает, что Дед Мороз может потратить на покупку его подарков не больше \(x\) рублей. Разумеется, он хочет получить как можно более дорогие подарки. Таким образом, он хочет выбрать два различных подарка с максимальной суммарной ценой, но при этом она не должна превышать \(x\).

Помогите Сене выбрать себе подарки.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(x\) (\(2 \le n \le 100\,000\), \(2 \le x \le 10^9\)). Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)). Гарантируется, что существует два подарка с суммарной ценой не больше \(x\).

Формат выходных данных
Выведите одно целое число: максимальную суммарную цену двух различных подарков, не превышающую \(x\).