Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.
Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью 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
Региональное отделение одного крупного банка заказало два несгораемых шкафа для хранения личных дел своих клиентов. Каждый шкаф имеет несколько ящиков различной высоты, при просмотре снизу вверх ящики в первом шкафу имеют высоту a1, a2, ..., am, а ящики во втором шкафу высоту b1, b2, ..., bn.
Шкафы были установлены в узкой нише в стене лицевой стороной друг к другу, поэтому оказалось, что выдвинуть одновременно два ящика, находящиеся напротив друг друга, невозможно. Сотрудники банка постоянно обращаются к личным делам клиентов, поэтому им удобнее держать ящики открытыми в течение рабочего дня. Поскольку пока клиентов у банка немного, использовать все ящики не обязательно. Решено было использовать такое множество ящиков, чтобы их все можно было выдвинуть одновременно и они не мешали друг другу. Чтобы максимально систематизировать работу, необходимо использовать как можно больше ящиков.
Помогите сотрудникам банка выбрать, какие ящики следует использовать.
Первая строка входного файла содержит два целых числа: m и n — количество ящиков в первом и во втором шкафу, соответственно (1 ≤ m, n ≤ 100000). Вторая строка содержит m целых чисел: a1, a2, ..., am высоты ящиков в первом шкафу. Третья строка содержит n целых чисел: b1, b2, ..., bn — высоты ящиков во втором шкафу. Высоты ящиков положительные и не превышают 109.
На первой строке входного файла выведите два числа k и l количество ящиков, которые следует использовать в первом и втором шкафу, соответственно. Сумму k + l вам следует максимизировать. На второй строке выведите k целых чисел номера ящиков в первом шкафу, которые следует использовать. На третьей строке выведите l целых чисел номера ящиков во втором шкафу, которые следует использовать. Если оптимальных решений несколько, выведите любое.
5 5 1 2 3 4 5 6 4 3 2 1
4 3 1 2 3 4 3 4 5
Директор школы «Лицей Программистов» города Линейска сумел привить ученикам этой школы хорошую дисциплину, но, несмотря на это, многие ученики продолжают опаздывать на уроки.
В Линейске есть всего одна главная улица, на которой расположен и сам лицей, и живут все его ученики. Дисциплинированные школьники выходят из своих домов в одно и то же время. Но, к сожалению, все они живут на разном расстоянии от школы и добираются с разной, но постоянной скоростью (среди учеников есть как весьма неторопливые, так и будущая чемпионка мира по бегу на 100 метров Маша Гайка).
Для улучшения ситуации с опозданиями школа купила один веломобиль, который взялся водить сторож школы. Веломобиль способен помимо водителя перевозить одного школьника. Веломобиль перемещается с постоянной скоростью \(v\).
Ночь веломобиль проводит в школьном гараже, а утром, ровно в тот момент, когда все ученики выходят из своих домов, отправляется им навстречу, чтобы подвезти какого-нибудь школьника. Конечно же, ему приходится подвозить школьника прямо до ворот школы, потому как никто не хочет быть высаженным посреди пути. После того, как веломобиль помог одному ученику быстрее добраться в учебное заведение, он снова может ехать навстречу следующему опаздывающему человеку.
Директор хочет начинать занятия как можно раньше, но для этого нужно, чтобы все ученики добрались до лицея. Он поручил вам помочь составить план, по которому должен действовать водитель веломобиля, чтобы время прибытия последнего школьника в школу было минимальным.
Первая строка входного файла содержит два целых числа \(n, v\) (\(1 \le n \le 10^5\), \(1 \le v \le 1000\)) — соответственно количество людей и скорость веломобиля. Следующие \(n\) строк содержат по два целых числа \(x_i, v_i\) (\(1 \le x_i, v_i \le 1000\)) — расстояния от школы до дома \(i\)-ого ученика и его скорость.
В первую строку выходного файла выведите вещественное число \(t\) — минимальное время, за которое все школьники доберутся до лицея. Во второй строке выходного файла выведите единственное число \(k\) — количество учеников, которых нужно подвезти. В следующих \(k\) строках выведите по два числа — номер школьника, которого нужно подвезти, и расстояние от школы, на котором этот школьник должен сесть в веломобиль.
Школьников нужно выводить в том же порядке, в котором они будут ехать на веломобиле.
Выводите все вещественные числа как можно точнее. При проверке вашего решения при сравнении вещественных чисел будет допускаться абсолютная или относительная погрешность \(10^{-6}\).
Пример5 4 1 1 4 2 3 1 7 5 5 1 | 2.400000000 2 5 4.000000000 3 0.800000000 |