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

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

В первой строке указано натуральное число \(N\) \((N < 100~000)\) – количество сканирований за сутки.

Следующие \(N\) строк содержат пары чисел: время начала и время окончания каждого сканирования (неотрицательные числа, меньшие \(86400000).\)

Запишите в ответе два натуральных числа: сначала найденное количество периодов, когда ни одно сканирование не проводилось, а затем их суммарную длительность (в мс).

Типовой пример организации данных во входном файле

\(5\)
\(10 \,\, 100\)
\(20 \,\, 120\)
\(130 \,\, 170\)
\(150 \,\, 200\)
\(250 \,\, 400\)

При таких исходных данных и длительности работы центра в \(500\) мс было \(4\) периода без сканирования: с \(0\) до \(10\) мс, с \(120\) до \(130\) мс, с \(200\) до \(250\) мс и с \(400\) до \(500\) мс. Их суммарная длительность равна $$(10 – 0) + (130 – 120) + (250 – 200) + (500 – 400) = 170.$$ Ответ для примера: \(4; \,\, 170.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Из соображений безопасности в одном самолёте может лететь только одна команда. Найдите способ доставить на соревнования максимально возможное число команд. Если способов несколько, то нужно выбрать такой, чтобы можно было доставить команду с максимальным числом участников.

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

В первой строке входного файла находятся два натуральных числа \(N\) \((N \leqslant 1000 )\) и \(M\) \((M \leqslant 1000 )\) — количество команд и количество самолётов соответственно. Следующие \(N\) строк содержат числа, обозначающие количество человек в команде, затем идут \(M\) строк, где указана пассажировместимость самолётов. Числа \(M\) и \(N\) могут быть не равны.

Запишите в ответе два натуральных числа: сначала максимальное количество команд, которые могут прибыть на соревнования, затем максимальную численность команды в этом случае.

В одном городе есть более \(100\) жилых домов. Все дома пронумерованы, начиная с единицы. Управляющая компания получила заявки на капитальный ремонт от жителей домов. В заявке указан номер дома и номер подъезда, где требуется ремонт, при этом каждой заявке присваивается уникальный идентификатор – натуральное число, не превышающее \(1~000~000.\) На один и тот же подъезд могут быть заявки сразу от нескольких жителей.

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

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

В первой строке входного файла находится натуральное число \(N\) \( (N \leqslant 200~000)\) – количество полученных заявок на капитальный ремонт. Следующие \(N\) строк содержат три числа: номер заявки, номер дома и номер подъезда (все числа натуральные, не превышающие \(1~000~000).\)

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

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

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из \(N\) участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков.

Для закупки доступно \(K\) моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.

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

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

Первая строка входного файла содержит два натуральных числа: \(N\) \((1 \leqslant N \leqslant 1~000~000)\) — количество участков СНТ и \(K\) \((1 \leqslant K \leqslant 100~000)\) — количество моделей снегоуборщиков соответственно. Следующие \(N\) строк содержат по одному натуральному числу, не превышающему \(1000,\) минимальные мощности снегоуборщиков, которые можно закупить для каждого из \(N\) участков. Далее в каждой из \(K\) строк содержится пара натуральных чисел — мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит \(1000,\) стоимость — \(100~000.\) Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.

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

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

Типовой пример организации данных во входном файле

\(3 \, 4\)
\(1\)
\(2\)
\(3\)
\(10 \, 7\)
\(1 \, 5\)
\(3 \, 7\)
\(2 \, 3\)

При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью \(2\) и стоимостью \(3,\) для третьего участка будет закуплен снегоуборщик мощностью \(10.\) Стоимость закупки составит \(3 + 3 + 7 = 13.\) Ответ: \(13; \,\, 10.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В магазине для упаковки подарков есть \(N\) кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Дана изначальная коробка, а одну коробку можно поместить в другую, если длина её стороны хотя бы на \(D + K\) единиц больше длины стороны другой коробки \((K\) — порядковый номер новой коробки в матрешке, нумерация с нуля). Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, при условии что длина стороны самой большой коробки, где будет находиться подарок, будет иметь минимально возможную длину.

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

В первой строке входного файла находится число \(N\) — количество коробок в магазине (натуральное число, не превышающее \(10~000),\) \(S\) — изначальная коробка (натуральное число, не превышающее \(10~000)\) и \(D\) (натуральное число, не превышающее \(1~000).\) В следующих \(N\) строках находятся значения длин сторон коробок (все числа натуральные, не превышающие \(10~000),\) каждое — в отдельной строке.

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

Типовой пример организации данных во входном файле

\(5 \, 26 \, 6\)
\(50\)
\(41\)
\(33\)
\(40\)
\(55\)

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон \(26,\) \(33,\) \(41,\) \(50\) или \(26,\) \(33,\) \(41,\) \(55,\) т.е. количество коробок равно \(4,\) а минимальная длина стороны самой большой коробки равна \(50.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

На соревнованиях по спортивному ориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами начиная с \(1.\) В начале сезона соревнований каждому спортсмену присваивается уникальный номер — натуральное число, не превышающее \(1~000~000.\) Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем. Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее число спортсменов с идущими подряд номерами.

Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки

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

В первой строке входного файла находится число \(N\) (натуральное число, не превышающее \(1~000~000)\) — количество посещений спортсменами контрольных точек в течение всего сезона соревнований. Каждая из следующих \(N\) строк содержит два натуральных числа, не превышающих \(1~000~000:\) номер спортсмена и номер посещённой им контрольной точки.

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

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

Типовой пример организации входных данных

\(9\)
\(41 \,\, 3\)
\(43 \,\, 125\)
\(50 \,\, 33\)
\(42 \,\, 125\)
\(42 \,\, 126\)
\(42 \,\, 127\)
\(41 \,\, 125\)
\(50 \,\, 126\)
\(42 \,\, 126\)

Для приведённого примера точку с номером \(125\) посетили три спортсмена с номерами \(41,\) \(42\) и \(43.\) Ответом является пара чисел: \(3 \,\, 125.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.