В некотором царстве, в некотором государстве было \(N\) городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |\(x_1\) - \(x_2\)| + |\(y_1\) - \(y_2\)|.
Император решил построить \(N\)+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Нелегкая задача выбрать место для столицы поручена Вам.
В первой строке вводится число \(N\) - количество городов (1 <= \(N\) <= 100). Следующие \(N\) строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.
8 0 0 1 0 2 0 0 1 2 1 0 2 1 2 2 2
1 1
4 0 0 1 1 0 1 1 0
0 -1
Байтмен владеет красивейшим садом в Байттауне, в котором он посадил n роз. Пришло лето, и цветы выросли большими и красивыми. Байтмен понял, что он не в состоянии самостоятельно ухаживать за всеми розами, и решил нанять двух садовников в помощь. В этом случае ему нужно выбрать две прямоугольные области, чтобы каждый из садовников ухаживал за розами в одной их них. Области не должны пересекаться, и в каждой должно быть ровно \(k\) роз.
Байтмен хочет установить забор, огораживающий прямоугольные области. Для экономии денег забор должен быть как можно короче. Ваша задача – помочь Байтмену выбрать две прямоугольные области.
Сад представляет собой прямоугольник длиной \(l\) метров и шириной \(w\) метров, который разделен на \(l\)·\(w\) одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (\(x\),\(y\)), удовлетворяющие ограничениям 1 <= \(x\) <= \(l\), 1 <= \(y\) <= \(w\). В каждом единичном квадрате может содержаться любое количество роз.
Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (\(l_1\),\(w_1\)), (\(l_1\),\(w_2\)), (\(l_2\),\(w_1\)) и (\(l_2\),\(w_2\)) (для 1 <= \(l_1\) <= \(l_2\) <= \(l\) и 1 <= \(w_1\) <= \(w_2\) <= \(w\)):
• содержит все единичные квадраты с координатами (\(x\),\(y\)), которые удовлетворяют условию \(l_1\) <= \(x\) <= \(l_2\) и \(w_1\) <= \(y\) <= \(w_2\), и
• имеет периметр 2 · (\(l_2\)−\(l_1\)+1)+ 2 · (\(w_2\)−\(w_1\)+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, если таких прямоугольников нет.
6 5 7 3 3 4 3 3 6 1 1 1 5 5 5 5 3 1
22
Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(X\)×\(Y\) метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось \(N\) круглых колонн, снести которые не представляется возможным.
Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.
В первой строке входных данных содержатся вещественные числа \(X\) и \(Y\), 1 <= \(X\), \(Y\) <= \(10^4\) . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (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\) + \(R_j\)). Все вводимые числа разделены пробелами.
Выведите три вещественных числа: \(X_F\), \(Y_F\) и \(R_F\) - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.
10 10 0
5.000 5.000 5.000
1 1000 0
0.500 0.500 0.500
10 10 4 1 1 1 9 9 1 1 9 1 9 1 1
5.000 5.000 4.657
Организаторы детского праздника планируют надуть для него \(M\) воздушных шариков. С этой целью они пригласили \(N\) добровольных помощников, \(i\)-й среди которых надувает шарик за \(T_i\) минут, однако каждый раз после надувания \(Z_i\) шариков устает и отдыхает \(Y_i\) минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).
В первой строке входных данных задаются числа \(M\) и \(N\) (0 <= \(M\) <= 15000, 1 <= \(N\) <= 1000). Следующие \(N\) строк содержат по три целых числа - \(T_i\), \(Z_i\) и \(Y_i\) соответственно (1 <= \(T_i\), \(Y_i\) <= 100, 1 <= \(Z_i\) <= 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 последовательность слов \(w_1\), \(w_2\), …, \(w_n\), такую, что для всех \(i\) от 1 до \(n\) – 1 слово \(w_i\) является собственным префиксом слова \(w_i\)+1.
Слово \(u\) длины \(k\) называется собственным префиксом слова \(v\) длины \(l\), если \(l\) > \(k\) и первые \(k\) букв слова \(v\) совпадают со словом \(u\). Например, «program» является собственным префиксом слова «programmer».
Задано множество слов \(S\) = {\(s_1\), \(s_2\), …, \(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\). Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.
3 zngs rjzr zng 3 3 1 1
1 2
6 gjnuitvaowpy gjnuitvaowpym gjnuitvaowp rjzrociinzeco tgbotnzepnvm aigqbzpnerv 9 2 3 1 2 3 1 2 3 1
2 4