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

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

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

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

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

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

Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество успешно решённых задач с подряд идущими номерами.

Во время сессии студенты сдают \(4\) экзамена, за каждый из которых можно получить от \(2\) до \(5\) баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по \(2\) балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.

Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые \(25 \%\) мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее \(25 \%\) студентов.

Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».

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

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

В первой строке входного файла находится число \(N\), обозначающее количество студентов (целое положительное число, не превышающее \(10~000\)). Каждая из следующих \(N\) строк содержит \(5\) чисел через пробел: ID студента (целое положительное число, не превышающее \(100~000\)) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов \(N\) кратно \(4\) и хотя бы один студент имеет более двух «двоек». Во входном файле все ID различны.

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

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

\(8\)
\(4 \, 4 \, 4 \, 4 \, 4\)
\(7 \, 5 \, 5 \, 5 \, 2\)
\(10 \, 3 \, 4 \, 4 \, 5\)
\(1 \, 4 \, 4 \, 4 \, 3\)
\(6 \, 3 \, 5 \, 5 \, 3\)
\(2 \, 2 \, 2 \, 2 \, 2\)
\(13 \, 2 \, 2 \, 2 \, 3\)
\(3 \, 3 \, 3 \, 3 \, 3\)

(Л. Шастин) Частная клиника работает круглосуточно, в режиме 24/7. В течение суток в клинике проводятся медицинские приёмы, каждый из которых характеризуется временем начала и окончания (в миллисекундах, прошедших с начала суток). Считается, что в миллисекунды начала и конца приема он ещё идет. Необходимо проанализировать загруженность врачей за сутки и определить периоды простоя, то есть такие отрезки времени, когда ни один приём не проходил.

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

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

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

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

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

\(6\)
\(10 \,\, 50\)
\(100 \,\, 150\)
\(110 \,\, 155\)
\(120 \,\, 160\)
\(130 \,\, 170\)
\(151 \,\, 170\)

При таких исходных данных и длительности работы клиники в \(200\) мс было три периода простоя: в отрезки времени с \(0\) по \(9\) мс, с \(51\) по \(99\) мс и с \(171\) по \(199\) мс. Их суммарная длительность равна \((10 - 0) + (100 - 51) + (200 - 171) = 88.\) Ответ для примера: \(3 \,\, 88.\) Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

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

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

\(5\)
\(10 \, 1070\)
\(230 \, 1070\)
\(240 \, 1070\)
\(1070 \, 1400\)
\(1071 \, 1400\)

При таких исходных данных в течение суток было \(7\) промежутков времени, когда число сотрудников не менялось: \((0, \, 10),\) \((10, \, 230),\) \((230, \, 240),\) \((240, \, 1070),\) \((1070, \, 1071),\) \((1071, \, 1400),\) \((1400, \, 1440).\) Наибольшей длиной из этих отрезков является число \(830.\) В \(1071\) минуту в предпоследний раз за сутки изменилось число сотрудников.

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

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

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

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

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером \(100~000\) на \(100~000\) точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от \(1\) до \(100~000\)) и номер позиции в ряду (целое число от \(1\) до \(100~000\)). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.

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

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

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