Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск по ответу
---> 56 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 >> Отображать по:
#1
Коровы - в стойла
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное рас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
#23
То березка, то рябина…
  

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья 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
#43
Лапта
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, D ≤ 1000, N ≤ 200). В следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, –1000 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, 0 < vi ≤ 1000), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (y ≥  0).

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

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

Оценка задачи

1 балл получат программы, которые верно работают, когда в поле не более двух соперников.

Примеры
Входные данные
10 2
1 1 1
-1 1 1
Выходные данные
9.05539
0.00000 10.00000
#406
Выборы
  
Источники: [ Командные олимпиады, ВКОШП, 2006, Задача D ]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
3
7 -1
2 8
1 2
Выходные данные
6
3
3 2 5
#414
Эльфы и олени
  
Источники: [ Командные олимпиады, ВКОШП, 2005, Задача B ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Даны эльфы, обладающие темпераментом Bi и олени со строптивостью Ai. С каждым оленем должны ехать два эльфа, причем Bk < Ai < Bj. Необходим выбрать наибольшее количество оленей.

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо \( b_j \lt a_i \lt b_k \), либо \( b_k \lt a_i \lt b_j\).

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

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

В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно \( (1 \le m, n \le 100 000) \).

Вторая строка содержит m целых чисел ai – строптивость оленей \( (0 \le a_i \le 10^9) \). В третьей строке записаны \(n\) целых чисел \(b_i\) – темперамент эльфов \( (0 \le b_i \le 10^9) \).

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

В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные
4 6
2 3 4 5
1 3 2 2 5 2
Выходные данные
2
1 1 2
2 4 5
#490
Очень Легкая Задача
  
Есть один листок и два ксерокса. Необходимо определить время, за которое можно получить N копий исходного листка. Первый ксерокс копирует страницу за X секунд, второй - за Y.

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

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

На вход программы поступают три натуральных числа N, x и y, разделенные пробелом (1 ≤ N ≤ 2∙108, 1 ≤ x, y ≤ 10).

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

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

Примеры
Входные данные
4 1 1
Выходные данные
3
Входные данные
5 1 2
Выходные данные
4
#497
Автобусы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Подзадачи и система оценки

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

Подзадача 1 (40 баллов)

В этой подзадаче \(N \leq 2000\)

Подзадача 2 (60 баллов)

Дополнительные ограничения отсутствуют.

Примеры
Входные данные
8 2
1 2
1 2
1 3
1 4
2 5
2 6
6 7
6 8
Выходные данные
1
6
Входные данные
8 2
5 3
1 2
1 3
1 4
2 5
2 6
6 7
6 8
Выходные данные
2
6
#566
Сад
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Байтмен владеет красивейшим садом в Байттауне, в котором он посадил 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
#585
Фонтан
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача C ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В прямоугольном зале с круглыми колоннами (координаты и радиусы колонн заданы) необходимо разместить круглый фонтан максимального радиуса.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(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
#586
Детский праздник
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача D ]
Для N человек известно 3 параметра: время надувания шарика, сколько шариков можно надуть до отдыха и время отдыха. Требуется определить, за какое минимальное время эти люди надуют N шариков.

Организаторы детского праздника планируют надуть для него \(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
#672
Провода
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= Li <= 10 000 000, все числа целые.

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

В первой строке находятся числа N и К. В следующих N строках - L1, L2, ..., LN, по одному числу в строке.

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

Вывести одно число - полученную длину отрезков.

Примеры
Входные данные
4 11
802
743
457
539
Выходные данные
200
#715
Морской бой
  
Заданы начальные координаты и скорости кораблей на плоскости. Есть бомбы, уничтожающие корабли на расстоянии не превышающем R от центра взрыва. Взрывать бомбы можно только в целые моменты времени. Требуется уничтожить все корабли наименьшим количеством бомб.

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

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

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

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

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

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

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

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

Комментарий. Решения, верно работающие при N ≤ 3, будут набирать не менее 50 баллов.

Примеры
Входные данные
3 3
-3 3 1 0
0 -6 0 2
-8 6 4 -1
Выходные данные
1
3 2.000 1.500
Входные данные
2 1
-4 -4 2 2
2 2 -2 -2
Выходные данные
2
0 -4.0000 -4.0000
0 2.0000 2.0000
#861
Медиана объединений
  

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

Напишите программу, которая для каждой пары последовательностей выведет левую медиану их объединения.

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

Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x1, d1, a, c, m. Элементы последовательности вычисляются по следующим формулам: x1 нам задано, а для всех i от 2 до L: xi = xi–1+di–1. Последовательность di определяется следующим образом: d1 нам задано, а для i≥2 di=((a*di–1+c) mod m), где mod – операция получения остатка от деления (a*di–1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 109.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример

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

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

Комментарии

3 6

1 3 1 0 5

0 2 1 1 100

1 6 8 5 11

7

10

9

Последовательности, объединения которых мы считаем, таковы:

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
#864
Медиана объединений
  
Дано N последовательностей. Требуется для каждой пары последовательностей найти медиану объединения этих последовательностей.

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

Напишите программу, которая для каждой пары последовательностей выведет левую медиану их объединения.

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

Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются последовательности. Каждая последовательность состоит из L чисел, по модулю не превышающих 30000.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример 

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

3 6

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
	

	

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

7

10

9
#887
Электрик-ковбой Джо
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Вот и сейчас ему поручили проверить два стоящих на расстоянии \(d\) друг от друга столба высоты \(h_1\) и \(h_2\) соответственно. Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.

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

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

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

Ковбой

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

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

Входной файл содержит четыре положительных целых числа: \(d\), \(h_1\), \(h_2\) и \(l\) - расстояние между столбами, высоту первого и второго столбов и максимальный допустимый перепад высот при прыжке, соответственно. Все числа во входном файле не превышают \(10^6\).

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

Выведите ответ с максимальной возможной точностью. Ответ будет проверяться с точностью до \(10^{-5}\).

Примеры
Входные данные
5 5 5 5
Выходные данные
10.0
Входные данные
4 5 8 5
Выходные данные
10.0
Входные данные
4 8 5 1
Выходные данные
13.0
Входные данные
3 4 6 1
Выходные данные
9.0
#894
Черепаха
  
Черепаха стоит на краю грядки. На грядки растут одуванчики, для каждого из них задано время и место всхода. Одуванчики прорастают последовательно, также задана скорость черепахи и время съедания одуванчика. Необходимо определить минимальное время, за которое можно съесть все одуванчики и вернуться.

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

Черепаха может ползти со скоростью, не превосходящей величины vmax. Одуванчик она съедает, остановившись на время d. Если одуванчик начать есть, но не доесть до конца, то он засыхает, поэтому его надо съедать за один прием. Одуванчики прорастают тем позже, чем дальше они расположены от начала грядки. В одной точке не могут прорастать несколько одуванчиков, а также несколько одуванчиков не могут прорастать в один момент времени.

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

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

В 1-й строке входного файла находятся 2 целых числа, разделенные пробелом: vmax (в см/мин) и d (в минутах), 0 < vmax ≤ 200, 0 ≤ d ≤ 500.

Во 2-й строке находится число N – количество одуванчиков (в штуках). 0 ≤ N ≤ 1400 при d = 0, в противном случае 0 ≤ N ≤ 200.

В каждой из последующих N строк расположены: целое число xi – расстояние от одуванчика до начала грядки (в сантиметрах), 0 ≤ xi ≤ 32767, и через пробел ti – момент прорастания одуванчика (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

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

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

Примечания

1. В часе – 60 минут, в сутках – 24 часа.

2. Время в сутках изменяется от 00:00 до 23:59.

3. Можете считать, что черепаха не меняет направления движения до тех пор, пока не доползет до последнего одуванчика.

Примеры
Входные данные
3 1 
1
100 00:01
Выходные данные
01:08
#957
Даша и кризис
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

\(\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}\)

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

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

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

В следующих \(n\) строках содержатся по два числа – \(v_i\) и \(w_i (0 \leq v_i \leq 10^6, 1 \leq w_i \leq 10^6\), обе суммы всех значений \(v_i\) и \(w_i\) не превосходят \(10^7\) каждая).

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

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

Примеры
Входные данные
3 2
1 1
1 2
1 3
Выходные данные
1
2
#963
Японский кроссворд
  

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

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

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

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

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

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

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

Примеры
Входные данные
3 4
3
3
2
1
Выходные данные
2
1
2
3
#1113
Интересные числа
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 210 = 102, 2410 = 110002.

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

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

Первая строка входного файла содержит два целых числа (1 ≤ n ≤ 1015, 2 ≤ k ≤ 10).

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

В выходной файл выведите n-ое в порядке возрастания число, запись которого в системе счисления с основанием k заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.

Примеры
Входные данные
1 2
Выходные данные
2
Входные данные
10 10
Выходные данные
110
#1126
Трамвайная остановка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На прямой расположены остановки с заданными координатами. Заданы скорость трамвая и мальчика. Требуется найти минимальное расстояние L до первой остановки, на которое мальчик должен видеть приближение трамвая так, чтобы трамвай не обогнал его между остановками.

Трамвайная линия имеет вид прямой. Петя живет в N трамвайных остановках от метро. Метро находится у нулевой остановки, в точке с координатой 0.


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

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

Во входном файле находятся три числа N, U и V (N ≤ 1000, U и V – положительные вещественные), за которым будет следовать N вещественных чисел – X1, X2,... Xn (0 < X1 < X2 < … < Xn < 106), разделенных пробелами.

 

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

В выходной файл ваша программа должна вывести число L с точностью до 10-4.

Примеры
Входные данные
1 1 10
2
Выходные данные
9.0000
#1227
Радио «Байтик»
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, при распространении радиоволн возникает интерференция, поэтому если рядом расположены две радиопередающие станции, вещающие на одной и той же частоте, то качество радиопередач резко снижается.

Радиостанция «Байтик» планирует транслировать свои программы в стране Флатландия. Министерство связи Флатландии выдало радиостанции лицензию на вещание на двух различных частотах.

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

Все передатчики, установленные на вышках, должны, согласно инструкции министерства, иметь одну и ту же мощность. Чтобы программы радиостанции могли приниматься на как можно большей территории, мощность передатчиков должна быть как можно большей. С другой стороны, необходимо, чтобы прием передач был качественным на всей территории Флатландии. Прием передач считается качественным, если не существует такого участка ненулевой площади, на который радиоволны радиостанции «Байтик» приходят на одной частоте одновременно с двух вышек.

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

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

Первая строка содержит число N — количество вышек (3 ≤ N ≤ 1200). Последующие N строк содержат по два целых числа — координаты вышек. Координаты заданы в километрах и не превышают 104 по модулю. Все точки, в которых расположены вышки, различны. Все числа в строках разделены пробелом.

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

В первой строке выводится вещественное число — искомая мощность передатчиков. Во второй строке выводятся N чисел, где i-е число должно быть равно 1, если соответствующий передатчик должен вещать на первой частоте, и 2, если на второй. Ответ должен быть выведен с точностью, не меньшей 10–8.

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.707106781186548
1 2 2 1
#1283
Сочи-2014
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

В строительстве объектов готовы участвовать K фирм. Фирмы имеют разные строительные мощности, выраженные в количестве денежных средств, которые фирма может осваивать в единицу времени.

В каждый момент времени фирма может осуществлять работы только на одном объекте. В строительстве одного объекта не могут одновременно участвовать несколько фирм. В любой момент времени любой объект может быть передан для продолжения строительства любой фирме.

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

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

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

Первая строка содержит целое число N — количество объектов (1 ≤ N ≤ 50). Во второй строке содержатся разделенные пробелами целочисленные значения S1, S2, S3, …, SN объемов денежных средств, выделяемых для строительства каждого из объектов. Числа Si выражены в тысячах рублей, положительные и не превышают 1000.

В третьей строке находится целое число K — количество строительных фирм (1 ≤ K ≤ 50). Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V1, V2, V3, …, VK в тыс.руб/час. Числа Vj положительные и не превышают 1000.

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

Первая строка содержит действительное число T — время в часах окончания всех работ, считая с начала строительства, выведенное не менее чем с тремя точными знаками после запятой. Далее в каждой строке содержатся разделенные пробелами три числа: t, i, j, где действительное число t — время от начала строительства в часах, в которое j-я фирма приступает к строительным работам на i-м объекте.

Значения времен необходимо выводить с максимально возможной точностью.

Строки должны быть отсортированы по неубыванию t.

Примеры
Входные данные
2
24 20
2
3 2
Выходные данные
8.800
0 1 1
0 2 2
6.4000000 1 2
6.4000000 2 1
Входные данные
3
100 100 100
4
5 5 10 10
Выходные данные
12.00000
0 1 3
0 2 4
0 3 1
4 2 2
4 3 4
8 1 1
8 3 4
8 2 3
#1341
Граффити на заборе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Плиты пронумерованы числами от 1 до N, граффити-художники имеют номера от 1 до M. Первоначально i-й граффити-художник находится около плиты с заданным номером pi. Каждому художнику требуется b минут на разрисовывание любой плиты. Каждую плиту должен разрисовать ровно один граффити-художник.

В начале работы, а также после разрисовывания любой плиты граффити-художник может перейти к любой неразрисованной плите. Время перемещения граффити-художника от любой плиты к соседней с ней одинаково и равно a минут. Таким образом, чтобы перейти от плиты с номером i к плите с номером j художнику требуется a×|i – j| минут.

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

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

В первой строке входного файла указаны числа N — количество плит в заборе и M — количество граффити-художников (1 ≤ N, M ≤ 100000). Во второй строке заданы два целых числа: a — количество минут, которое требуется для перехода от любой плиты к соседней, и b — количество минут, которое требуется граффити-художнику на разрисовывание одной плиты (1 ≤ a, b ≤ 106). В третьей строке заданы M чисел p1, p2, …, pM — начальные положения граффити-художников (1 ≤ pi ≤ N).

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

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

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

Примечание

Решения, корректно работающие при M ≤ 2, будут оцениваться из 40 баллов.

Примеры
Входные данные
10 2
19 56
9 2
Выходные данные
375
5 10 9 8 7 6 
5 1 2 3 4 5
#1387
Предпраздничная суета
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.

В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется Ai единиц времени на обработку одного товара и Bi единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет Ti единиц времени.

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

Напишите программу, которая определит это минимальное время.

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

В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).

Все числа во входном файле целые.

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

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

Комментарии к примерам тестов

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

Выгоднее всего одному из школьников встать со всеми тортиками в первую кассу, а остальным выйти без покупок.

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.

Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.

Примеры
Входные данные
2
100 10 40
10 100 50
2 2
Выходные данные
160
Входные данные
3 
1 2 0
5 2 1
2 10 1
3 5
Выходные данные
7
#1620
Субботник
  

В классе учатся N человек. Классный руководитель получил указание направить на субботник R бригад по С человек в каждой.

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

Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по три человека в каждой. Тогда одним из вариантов является такой:

1 бригада: люди с ростом 225, 205, 225

2 бригада: люди с ростом 160, 190, 170

При этом число неудобства первой бригады будет равно 20, а число неудобства второй — 30. Максимальное из чисел неудобств будет 30, и это будет наилучший возможный результат.

Формат входных данных

Сначала вводятся натуральные числа N, R и C — количество человек в классе, количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ N ≤ 100 000). Далее вводятся N целых чисел — рост каждого из N учеников. Рост ученика — натуральное число, не превышающее 1 000 000 000.

Формат выходных данных

Выведите одно число — наименьше возможное значение максимального числа неудобства сформированных бригад.

Примеры
Входные данные
8 2 3
170
205
225
190
260
130
225
160
Выходные данные
30
#1722
Морской бой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Совсем недавно появилась в продаже новая компьютерная игра «Морской бой—3». Вася купил себе эту игру и теперь играет в нее в свободное от занятий время. Особенно ему нравится в одной из миссий управлять самолетом. Изначально самолет находится на палубе неподвижного авианосца и готов в любой момент к взлету. Задача игрока в этой миссии состоит в уничтожении \(N\) кораблей противника. После уничтожения всех кораблей самолет должен вернуться обратно на авианосец.

Для простоты будем считать плоской поверхность моря, где располагается авианосец. Введем прямоугольную декартову систему координат и разместим авианосец в начале координат. Каждый из кораблей в начальный момент игры находится в некоторой точке (\(x\), \(y\)), и сразу после начала игры движется равномерно и прямолинейно так, что его вектор скорости равен (\(V_x\), \(V_y\)).

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

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

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

Первая строка входного файла содержит число \(N\), определяющее количество кораблей (1 \(\le\) \(N\) \(\le\) 9). Вторая строка входного файла содержит целое число \(U\) (1 \(\le\) \(U\) \(\le\) 10000), задающее скорость самолета в метрах в секунду. Последующие \(N\) строк описывают все корабли. Каждая строка содержит четыре целых числа \(x\), \(y\), \(V_x\), \(V_y\), не превосходящих 10000 по модулю и определяющих начальные координаты и скорость корабля, соответственно. Координаты кораблей заданы в метрах, скорости — в метрах в секунду.

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

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

В первой строке выходного файла выведите минимальное время, требуемое на выполнение миссии. Требуемая точность — не менее \(10^{−3}\).

Примеры
Входные данные
1
1000
10 10 0 0
Выходные данные
0.0282842712474619
#1920
Квадратик
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На клетчатом поле \(N\times N\), некоторые клетки которого закрашены, требуется найти размер максимального квадрата, состоящего из закрашенных клеток.

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

В первой строке входного файла содержится единственное целое число \(N\) (\(1\le N\le 3\,000\)). В каждой из следующих \(N\) строк содержится по \(N\) символов «#» и «.» (соответствующих закрашенным и незакрашенным клеткам соответственно), описывающих таблицу.

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

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

Система оценки

Каждая программа тестируется на четырёх тестах:

чтобы пройти первый тест, достаточно написать решение, работающее за \(O(N^5)\), чтобы пройти второй, требуется решение уже за \(O(N^4)\), третий — за \(O(N^3)\), четвёртый — за \(O(N^2\log N)\).

За каждый успешно пройденный тест начисляется 25 баллов.

Посылка, набирающая \(x\) баллов по сумме баллов за тесты, считается принятой, если выполняются следующие два условия:

* во-первых, если \(x>25\), должна существовать более ранняя принятая посылка, балл за которую по сумме баллов за тесты равен \(x-25\),

* во-вторых, программа не должна содержать отсечений по \(N\), искусственных замедлений работы и т. п.

Если посылка не принята, через некоторое время после её отправки результат её проверки станет «Дисквалифицирован». Балл за принятую попытку вычисляется как сумма баллов за каждый тест минус 5 баллов за каждую более раннюю дисквалифицированную посылку.

Задача считается решённой, если существует принятая посылка, получившая не менее 100 баллов.

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

#1923
Дипломы
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось \(n\) дипломов, причём, как оказалось, все они имели одинаковые размеры: \(w\) — в ширину и \(h\) — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером \(w\) на \(h\). Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

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

Входной файл содержит три целых числа: \(w\), \(h\), \(n\) (\(1\le w,h,n\le 10^9\)).

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Иллюстрация к примеру
Примеры
Входные данные
2 3 10
Выходные данные
9
Входные данные
1 1 1
Выходные данные
1
#1967
Транспортировка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.

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

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами. 

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик -  3 тонны.

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

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

Примеры
Входные данные
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
Выходные данные
2
#2890
Пастух
  
Бинпоиск по углу. Пересекаем бублики и ГМТ из которых какие-нибудь две овцы видны под зафиксированным углом.
#2967
Когда корень не равен корню
  

Найдите наименьшее натуральное число x, такое что math.sqrt(x*x) != x.

(Предполагается, что вы используете python3!)

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

отсутствует

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

Одно натуральное число.

#2969
Дракон
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Король Флатландии понял, что дальше так продолжаться не может, и нанял отважного Рыцаря, чтобы тот победил рептилию.

Рыцарь принял предложение Короля и начал готовиться к битве. Сам он участия в битве принимать не желал (не рыцарское это дело –– мечом махать), поэтому решил собрать войско из копейщиков. Но копейщикам надо платить, а у Рыцаря из-за кризиса осталось совсем немного сбережений. Помогите ему определить минимальное число копейщиков, необходимое для победы над Черным Драконом.

У копейщика и у дракона есть два параметра: количество очков здоровья и наносимый противнику урон.

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

Требуется написать программу, которая определяет минимальное количество копейщиков, которое необходимо нанять Рыцарю, чтобы победить Черного Дракона.

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

Вводятся четыре натуральных числа через пробел: Hd, Dd, hp, dp –– количество очков здоровья дракона, урон, наносимый драконом, количество очков здоровья одного копейщика и урон, наносимый одним копейщиком. Все числа положительные и не превосходят 109.

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

Выведите на экран одно целое число –– минимальное число копейщиков, необходимое для победы над драконом.

Примеры
Входные данные
500 50 10 10
Выходные данные
20
Входные данные
500 28 10 10
Выходные данные
15
#3334
Проходной балл
  

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

  1. Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
  2. Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
  3. Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
  4. На второй тур можно пригласить не более \(M\) участников.

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

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

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

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

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

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

Примечания

Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).

  1. Тест 1 из условия, оценивается в 0 баллов.
  2. В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le R \le M \le 10\,000\), \(M < N \le 100\,000\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. В тестах этой группы, \(1 \le R \le M < N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.
Примеры
Входные данные
9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0
Выходные данные
985
#3380
Лифт
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Высокое здание, состоящее из \(N\) этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от \(1\) до \(N\) снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна \(A_i\). Известно, что лифт не может перевозить более \(C\) человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется \(P\) секунд. Какое наибольшее количество человек лифт может перевезти на парковку за \(T\) секунд, если изначально он находится на уровне парковки?

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

В первой строке входного файла содержатся целые числа \(N\), \(C\), \(P\), \(T\) (\(1 \leq N \leq 100\), \(1 \leq C \leq 10^9\), \(1 \leq P \leq 10^9\), \(1 \leq T \leq 10^9\)). Вторая строка содержит последовательность \(N\)  целых чисел \(A_1\), \(A_2\), ..., \(A_N\) (\(0 \leq A_i \leq 10^9\)). Сумма всех значений последовательности не превосходит \(10^9\).

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

Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.

Примеры
Входные данные
4 5 2 15
0 1 2 3
Выходные данные
3
Входные данные
4 5 2 18
0 1 2 3
Выходные данные
5
Входные данные
3 2 1 9
1 1 1
Выходные данные
3
#3381
Коровники
  

В селе Максоярославке коровы обычно пасутся на лужайках, соединенных дорожками, на каждой лужайке пасется хотя бы одна корова. При этом для каждой пары лужаек есть ровно один способ пройти от одной лужайки до другой. По каждой дорожке можно двигаться в обоих направлениях. Считается, что все дорожки имеют одинаковую длину.
Главный фермер села хочет построить на лужайках \(k\) коровников для своих коров. Ясно, что каждая корова вечером будет возвращаться именно в тот коровник, который ближе к ее лужайке (если расстояние до коровников одинаково, то в любой из них). Поэтому возникает задача определения такого расположения коровников, при котором наибольшее из расстояний, проходимых коровами, было бы минимально.

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

В первой строке входного файла содержатся два числа \(n\) и \(k\) (\(2 \le n \le 50\;000\), \(1 \le k \le n\)) --- количество лужаек и планируемое число коровников, соответственно. Следующие \(n - 1\) строк содержат описания дорожек. Каждая дорожка задается парой целых положительных чисел (\(a, \, b\)), где \(a\) и \(b\) --- номера лужаек, которые соединяет данная дорожка. Лужайки нумеруются с единицы.

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

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

Примеры
Входные данные
7 2
5 4
4 3
1 3
2 3
4 6
6 7
Выходные данные
2
1 4
#3386
Йою Ньерк
  
#3398
Велогонка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на \(x_1\), \(x_2\), ..., \(x_n\) метров (\(n\) – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью \(v_1\), \(v_2\), ..., \(v_n\) метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов \(n\), заданным начальным положениям велосипедистов \(x_1\), \(x_2\), ..., \(x_n\) и их скоростям \(v_1\), \(v_2\), ..., \(v_n\), вычислит момент времени \(t\), в который расстояние \(l\) между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число \(n\) – количество велосипедистов.

В последующих n строках указаны по два целых числа: \(x_i\) – расстояние от старта до \(i\)-го велосипедиста в начальный момент времени (\(0 \leq x_i \leq 10^7\)) и \(v_i\) – его скорость (\(0 \leq v_i \leq 10^7\)).

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

В выходной файл необходимо вывести два вещественных числа: \(t\) – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, \(l\) – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более \(10^{–6}\), что означает следующее. Пусть выведенное число равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет считаться правильным, если значение выражения \(|x – y| / max(1, |y|)\) не превышает \(10^{–6}\).

Подзадачи и система оценки

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

Подзадача 1 (20 баллов)

\(2 \leq n \leq 50\), \(0 \leq  x_i \leq 1000\), \(0 \leq v_i \leq 1000\). Гарантируется, что существует ответ, в котором \(t\) – целое число, не превышающее 1000.

Подзадача 2 (20 баллов)

\(2 \leq n \leq 200\).

Подзадача 3 (30 баллов)

\(2 \leq n \leq 2000\)

Подзадача 4 (30 баллов)

\(2 \leq n \leq 10^5\)

Примеры
Входные данные
3
0 40
30 10
40 30
Выходные данные
1 30
Входные данные
5
90 100
100 70
100 70
110 60
120 35
Выходные данные
0.5 5.000000000000
#3870
Космический кегельбан
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. В последнем n-м ряду стоит n кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке (0, 0). Центры кеглей во втором ряду находятся в точках (–1, 1) и (1, 1). Таким образом, центры кеглей в i-м ряду находятся в точках с координатами (–(i – 1), i –  1), (–( i – 3), i – 1), …, (i – 1, i – 1).

Игра происходит следующим образом. Используется шар с радиусом q метров. Игрок выбирает начальное положение центра шара (xc,  yc) и вектор направления движения шара (vx, vy). После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора (vx, vy). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.

На рисунке приведен пример расположения кеглей для r = 500, n = 4 и шара для q = 1000, xc = –2, yc = –2, vx = 1, vy = 1.

Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению ( xc, yc) и вектору направления движения (vx,  vy) определяет количество кеглей, сбитых шаром.

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

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (1 ≤ r ≤ 700, 1  ≤ n ≤ 200 000).

Вторая строка входного файла содержит целое число q (1  ≤ q ≤ 109).

Третья строка входного файла содержит два целых числа xc и yc, разделенных ровно одним пробелом (–106≤ xc ≤ 106, –10 6≤ yc, 1000 ×yc < –(r + q) ).

Четвертая строка входного файла содержит два целых числа vx и vy, разделенных ровно одним пробелом (–106≤ vx ≤ 106, 0  < vy ≤ 106).

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

Выходной файл должен содержать одно целое число — количество сбитых кеглей.

Примечание

Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).

Система оценки

Потестовая.

Примеры
Входные данные
500 4
1000
-2 -2
1 1
Выходные данные
7
#111402
Веревочки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С утра шел дождь, и ничего не предвещало беды. Но к обеду выглянуло солнце, и в лагерь заглянула СЭС. Пройдя по всем домикам и корпусам, СЭС вынесла следующий вердикт: бельевые веревки в жилых домиках не удовлетворяют нормам СЭС. Как выяснилось, в каждом домике должно быть ровно по одной бельевой веревке, и все веревки должны иметь одинаковую длину. В лагере имеется \(N\) бельевых веревок и \(K\) домиков. Чтобы лагерь не закрыли, требуется так нарезать данные веревки, чтобы среди получившихся веревочек было \(K\) одинаковой длины. Размер штрафа обратно пропорционален длине бельевых веревок, которые будут развешены в домиках. Поэтому начальство лагеря стремиться максимизировать длину этих веревочек.

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

В первой строке заданы два числа — \(N\) (\(1 \le N \le 10001\)) и \(K\) (\(1 \le K \le 10001\)). Далее в каждой из последующих \(N\) строк записано по одному числу — длине очередной бельевой веревки. Длина веревки задана в сантиметрах. Все длины лежат в интервале от \(1\) сантиметра до \(100\) километров включительно.

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

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

Примеры
Входные данные
4 11
802
743
457
539
Выходные данные
200
#111491
Березовая аллея
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной \(W\) метров. Вдоль левой стороны аллеи растет \(N\) берез, а вдоль правой — \(M\) берез, при этом \(i\)-я береза с левой стороны аллеи находится на расстоянии \(a_i\) метров от начала аллеи, а \(j\)-я береза с правой стороны — на расстоянии \(b_j\) метров от начала аллеи.

Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы. Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой (зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию. К сожалению, в его распоряжении оказалась только лента длиной \(L\) метров, которую, к тому же, нельзя было разрезать. Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез. При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.

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

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

Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты \(L\) и ширину аллеи \(W\) (\(1 \leq L \leq 2 \times 10^5\), \(1 \leq W \leq 10^4\)).

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число \(N\) — количество берез (\(1 \leq N \leq 2000\)), а третья строка содержит \(N\) различных целых чисел \(a_1\), \(a_2\), …, \(a_N\) (\(0 \leq a_i \leq 10^5\)), заданных по возрастанию.

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число \(M\) — количество берез (\(1 \leq M \leq 2000\)), а пятая строка содержит \(M\) различных целых чисел \(b_1\), \(b_2\), …, \(b_M\) (\(0 \leq b_i ≤ 10^5\)), заданных по возрастанию.

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

Выходной файл должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой.

Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + \(10^{-5}\)).

Система оценивания

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 50, будут оцениваться из 30 баллов.

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 500, будут оцениваться из 60 баллов.

Примеры
Входные данные
18 4
3
0 3 6
4
0 3 6 10
Выходные данные
5
Входные данные
5 3
1
0
1
0
Выходные данные
0
#111572
Военный полигон
  
Ограничение по времени, сек0.75
Ограничение по памяти, мегабайт256





Министерство обороны Флатландии планирует построить новый военный полигон. Полигон должен иметь форму круга.

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

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

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

Первая строка входного файла содержит число \(N\) — количество силовых щитов. Каждая из следующих N строк описывает силовой щит (\(1 \leq N \leq 200000\)). Описание представляет собой четверку координат: \(x_{min}\), \(y_{min}\), \(x_{max}\), \(y_{max}\). Все координаты целые и не превышают 100000 по абсолютной величине.

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

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

Если построить полигон невозможно, выведите “Impossible” на первой строке выходного файла.

Примеры тестов
Входные данные
4
0 0 2 3
1 -1 4 1
1 1 4 4
2 0 5 5
Выходные данные
3.0 2.0 1.0
Входные данные
1
0 0 1 1
Выходные данные
Impossible
Входные данные
2 
0 0 3 3
0 0 3 3
Выходные данные
1.5 1.5 1.5
Решения, работающие при \(1 \leq N \leq 5 000\), будут набирать не менее 50 баллов
#111704
Калитка в заборе
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали 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 \le n \le 8000\). Группа оценивается в 40 баллов.

Для всех тестов второй группы выполняются ограничения \(1 \le n \le 100000\). Группа оценивается в 40 баллов.

Для всех тестов третьей группы выполняются ограничения \(1 \le n \le 1000000\). Группа оценивается в 20 баллов.

Примеры
Входные данные
3 2
2 6
3 4 5
Выходные данные
1
1
Входные данные
3 2
1 6
4 3 5
Выходные данные
0
Входные данные
3 5
1 7
5 3 4
Выходные данные
3
2
3
1
#111725
Домофон
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

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

При интенсивном использовании домофона краска, нанесённая на цифровые клавиши, постепенно стирается. Одна из компаний, занимающихся установкой домофонов, заинтересовалась возможностью определить диапазон номеров квартир, расположенных в подъезде, по тому, насколько стёрлась краска с клавиш. Они уже обнаружили, что по состоянию клавиши можно определить, сколько раз эту клавишу нажимали. Теперь вам, программисту этой компании, поручили для начала решить простейший вариант задачи восстановления диапазона квартир по «затёртостям». А именно, вашей программе на вход даются 10 чисел — «затёртости» клавиш 0, 1, ..., 9,  т. е. количество раз, которое нажималась соответствующая клавиша. Считая, что за время использования домофона каждую квартиру набрали ровно один раз, и считая, что номера квартир в подъезде начинаются с 1 (т. е. в подъезде расположены квартиры с номерами 1, 2, ..., N при некотором N), определите диапазон квартир в этом подъезде (т. е., фактически, определите это N). Считайте, что посетители никогда не набирают ведущих нулей. Считайте, что N не может превосходить 109.

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

На первой строке входного файла находятся 10 чисел – затёртости цифр 0, 1, ..., 9. Все затёртости не превышают 109; гарантируется, что есть хотя бы одна ненулевая затёртость.

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

В выходной файл выведите одно число N. Если подходящего набора диапазона квартир не существует, выведите одно число  - 1. Если подходящих N существует несколько, выведите любое. Гарантируется, что, если искомое N существует, то оно не превосходит 109.

Примеры
Входные данные
1 2 1 1 1 1 1 1 1 1
Выходные данные
10
Входные данные
2 4 2 2 2 2 2 2 2 2
Выходные данные
-1
Входные данные
1 1 0 0 0 0 0 0 0 0
Выходные данные
-1
Входные данные
1 0 0 0 0 0 0 0 0 0
Выходные данные
-1
Входные данные
162 273 270 263 263 263 263 262 189 162
Выходные данные
826
#111734
Загулявшие гости
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

N гостей засиделись на даче и боятся опоздать на последнюю электричку. У хозяина дачи, который остается на ночь, есть автомобиль, но в него могут сесть одновременно не более 4 человек, не считая шофера. Скорость движения автомобиля по лесной дороге  V км/ч, скорость движения пешехода  U км/ч, расстояние от дачи до железнодорожной станции Z км, затратами времени на посадку-высадку пассажиров и разворот автомобиля можно пренебречь. За какое минимальное время все гости доберутся до станции?

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

В единственной строке заданы значения величин N, V, U и Z, разделенными одним или несколькими пробелами. Числа V, U и Z — положительные вещественные и не превосходят 100, (1 ≤ N ≤ 30).

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

Выведите искомое значение времени с точностью до 10 - 3.

Примеры
Входные данные
8 30 5 15
Выходные данные
1.0555555556
#111787
Наибольший квадрат
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дан двумерный массив целых чисел n × m, все элементы которого — нули или единицы. Найти в нём наибольший по площади квадрат, состоящий только из единиц. Гарантируется, что в нём есть хотя бы одна единица.

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

Вводятся два целых числа n и m (1 ≤ n, m ≤ 1000), а потом n строк по m чисел 0 или 1 — элементы массива.

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

Вывести три числа — длину стороны квадрата и координаты его левого верхнего угла.

Примеры
Входные данные
1 1
1
Выходные данные
1
1 1
Входные данные
3 5
1 1 0 0 0
1 1 1 1 1
0 0 0 1 1
Выходные данные
2
1 1
#111790
Экзамен
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла содержится два целых числа N, D (1 ≤ N ≤ 10000; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ..., XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента

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

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

Примеры
Входные данные
4 1
11 1 12 2
Выходные данные
2
1 1 2 2
Входные данные
4 0
11 1 12 2
Выходные данные
1
1 1 1 1
#111879
Чет-нечет
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите \(N\)-й элемент этой последовательности.

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

Одно целое число \(N\) (1 \(\le\) \(N\) \(\le\) 10100).

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

Выведите одно целое число - \(N\)-й элемент последовательности.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
4
Выходные данные
5
#111893
Бюджет
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Всем известно, что основной целью любого крупного правительственного проекта во Флатландии является освоение бюджетных средств (разумеется, по назначению). В настоящее время во Флатландии ведется работа над m национальным проектами, i-й проект может освоить \(s_i\) миллионов Флатландских тугриков в день.

Правительство Флатландии планирует выделить \(n\) грантов для финансирования проектов, каждый по p миллионов Флатландских тугриков. Деньги i-го из грантов будут доступны для освоения, начиная с дня \(r_i\). Когда очередной грант становится доступен для освоения, его можно отдать некоторому проекту. Этот проект осваивает деньги гранта в течение \(\lceil\frac{p}{s_i}\rceil\) дней. Проект не может одновременно осваивать деньги нескольких грантов.

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

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

Первая строка входного файла "budget.in" содержит числа m, n и p (1 ≤ m ≤ 100, 1 ≤ n ≤ 100, 1 ≤ p ≤ \(10^9\)). Вторая строка содержит m целых чисел: \(s_1\), \(s_2\), . . . , \(s_m\) (1 ≤ \(s_i\) ≤ \(10^9\)). Третья строка содержит n целых чисел: \(r_1\),\(r_2\),...,\(r_n\) (1 ≤ ri ≤ \(10^9\)).

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

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

Примечание

Одна из возможных оптимальных схем освоения устроена следующим образом: грант 1 отдается первому проекту, который осваивает его в течение 11 дней. Остальные гранты отдаются второму проекту, грант 2 осваивается в течение дней 3–7, грант 3 в течение дней 8–12 и грант 4 в течение дней 13–17. Заметим, что грант 4 появляется в день 12, но назначается только в день 13.

Примеры
Входные данные
2 4 22
2 5
1 3 8 12
Выходные данные
17
#112095
Игорь и игрушки
  
ограничение по времени на тест
2.5 second;
ограничение по памяти на тест
512 megabytes

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

При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.

Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.

Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.

Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.

Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.

Формат входного файла

В первой строке содержится натуральное число \(N\) (1 ≤ \(N\) ≤ 100 000) - количество игрушек. Далее следуют описания \(N\) выпуклых многоугольников в следующем формате: сначала идет натуральное число \(k_m\) (3 ≤ \(k_m\) ≤ 300 000) - количество вершин в \(m\)-м многоугольнике, затем идут \(k_m\) строк, в которых записаны пары целых чисел xm,s, ym,s, по модулю не превосходящих \(10^9\) - координаты вершин \(m\)-го многоугольника в порядке обхода против часовой стрелки, заданные в системе координат соответствующей ему коробки, которая стоит на столе (это означает, что ym,s >= 0, а также для всех игрушек существует вершина \(v_m\), у которой ym,\(v_m\) = 0). Сумма всех \(k_m\) (обозначим ее за \(S\)) не превосходит 300 000.

В следующей строке записано натуральное число \(Q\) (1 ≤ \(Q\) ≤ 500 000) - число вариантов. Следующие \(Q\) строк содержат пары натуральных чисел \(i_t\), \(j_t\) (1 ≤ \(i_t\) < \(j_t\) ≤ \(N\)) - номера сдвигаемых игрушек в очередном варианте.

Формат выходного файла

Выведите \(Q\) строк: для каждого варианта выбора пары одно вещественное число - необходимую ширину коробки. Ответ будет считаться правильным, если все числа посчитаны с абсолютной или относительной погрешностью не более \(10^{-9}\).

Комментарий

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

Система оценивания

Тесты к этой задаче состоят из четырех групп.

0. Тест 1. Тест из условия, оценивается в ноль баллов.

1. Тесты 2–20. В тестах этой группы \(k_m\) ≤ 100, \(Q\) ≤ 1 000, \(S\) ≤ 10 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы.

2. Тесты 21–40. В тестах этой группы \(k_m\) ≤ 300, \(Q\) ≤ 50 000, \(S\) ≤ 100 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае про- хождения всех тестов из первой группы.

3. Тесты 41–65. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры
Входные данные
2
5
0 0
4 2
6 6
3 8
-2 4
5
0 0
2 0
8 4
5 11
3 12
1
1 2
Выходные данные
14.5000000000
Входные данные
2
3
0 0
0 3
-1 1
3
0 0
1 0
-20 20
1
1 2
Выходные данные
21.0000000000
#112554
Подстрока
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

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

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

Примеры
Входные данные
3 1
abb
Выходные данные
2 1
Входные данные
5 2
ababa
Выходные данные
4 1
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест