Дано 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
Джо - электрик-ковбой. Как у всех ковбоев у него есть лассо, как всем электрикам ему иногда приходиться залезать на столбы, и как все он ленив.
Вот и сейчас ему поручили проверить два стоящих на расстоянии \(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
Пусть A — массив, состоящий изNэлементов A1,...,AN. Обозначим его максимальноеи минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S=A1+A2+…+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1iN. Такое преобразование массива A назовем операцией Confuse. Напишите программу, которая по массиву B, полученному в результате K–кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).
Первая строка входного файла содержит целые числа N и K, где N — количество элементов массива B (2 N 10000), а K — количество применений операции Confuse к начальному массиву A, 1 K 100. Вторая строка файла содержит N элементов массива B. Элементы массива B — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.
Единственная строка выходного файла должна содержать целое число - разность max(A) и min(A).
4 2 45 52 47 46
7
Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики – ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени, и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.
Черепаха может ползти со скоростью, не превосходящей величины 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
Даша имеет \(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