Банк заданий
ЕГЭ по информатике

В кондитерской есть $N$ круглых форм для коржей. Специализация кондитерской – многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 8 единиц меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.

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

В первой строке входного файла находится число $N$ — количество форм для коржей в кондитерской (натуральное число, не превышающее 10000). В следующих $N$ строках находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10000), каждое - в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.

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

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

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

5

43

40

32

40

30

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

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

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/27779_26.txt

На грузовом космическом корабле необходимо перевезти на МКС контейнеры, имеющие одинаковые габариты и разные массы. Общая масса всех этих контейнеров превышает грузоподъёмность космического корабля. Количество грузовых мест на космическом корабле не меньше числа контейнеров, назначенных к перевозке.

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

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

В первой строке входного файла находятся два числа: $S$ - грузоподъёмность космического корабля (натуральное число, не превышающее 100000) и $N$ - количество контейнеров (натуральное число, не превышающее 10000). В следующих $N$ строках находятся значения масс контейнеров, требующих транспортировки на МКС (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

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

100 4

80

30

50

40

При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров - 30 и 40, 30 и 50 или 40 и 50. Контейнеры с массами 50 и 80 могут быть не перевезены. Ответом для приведённого примера является пара чисел 2 и 130.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/27636_26.txt

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

Алгоритм формирования рейтинга выглядит следующим образом:

- все $2*N$ чисел, обозначающих продолжительности работы в режиме ожидания и в режиме активного использования для N устройств, располагаются по возрастанию;

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

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

- показатели устройств, ранее включённых в рейтинговый список, игнорируются.

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

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

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

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

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

5

800 120

150 200

250 300

60 100

180 220

Пример организации данных приведён для пяти смартфонов.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/25363_26.txt

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

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

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

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

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

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/24897_26.txt

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

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

Примечание. Чем меньше числовое значение ряда, тем ближе ты к экрану.

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

В первой строке входного файла записаны два числа $N$ и $K$: $N$ — общее количество кинозалов в кинотеатре; $K$ — количество проданных билетов призракам. Следующие $N$ строк - информация о кинозалах (3 числа) - сначала номер кинозала, затем количество рядов в нём, затем количество мест в ряду в этом кинозале. В следующих $K$ строк содержится информация о забронированных местах призраками - сначала номер кинозала, затем ряд в нём, затем номер места в ряду в этом кинозале занятое призраком.

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

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

1 5

1 6 6

1 1 1

1 1 6

1 2 3

1 3 1

1 5 5

Для данного примера ответом будет: 3 3 (3 ряд - минимальный, где помещается 5 друзей, а варианты купить билеты у друзей были: 1 вариант на 3-м ряду и два варианта на 6 ряду).

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/24624_26.txt

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

В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:

– все $2*N$ чисел, обозначающих срок хранения и срок годности к употреблению для $N$ продуктов, упорядочивают по возрастанию;

– если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от

его начала;

– если минимальное число – срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;

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

Этот алгоритм применяется последовательно для размещения всех $N$ продуктов.

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

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

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

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

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

5

30 50

100 155

150 170

10 160

120 55

При таких исходных данных порядок расположения продуктов в рейтинге следующий: 4, 1, 2, 3, 5. Последним займёт своё место в рейтинге продукт 3. При этом один продукт займёт в рейтинге более низкое место.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23765_26.txt

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

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

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

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

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

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

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

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

3 4

1

2

3

10 7

1 5

3 7

2 3

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

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23570_26.txt

На соревнованиях по спортивнориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер - натуральное число, не превышающее 1000000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем.

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

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

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

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

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

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

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.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23383_26.txt

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

Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

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

В первой строке входного файла находится натуральное число $K$, не превышающее 1000, - количество окон в МФЦ. Во второй строке натуральное число $N$ ($N ≤ 10 000$), обозначающее количество граждан. Каждая из следующих $N$ строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в заявке время начала и время окончания приёма (в минутах от начала суток).

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

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

2

5

30 60

40 100

59 60

61 100

101 144

При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, - 1, так как будут свободны окна 1 и 2.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23283_26.txt

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

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

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

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

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

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

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

5 6

174095

154513

136531

170874

214313

156563

154846

189143

139135

138431

241337

При таких исходных данных максимальное количество экипажей, которые смогут покататься на санках, равно 4, если взять экипажи массой 136531, 154513, 170874 и 174095 соответственно. Максимальный экипаж можно взять равным 214313.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23259_26_15.txt

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

На ленте транспортёра имеется $N$ мест для каждой из $N$ деталей.

На ленте транспортёра детали располагают по следующему алгоритму:

— все $2*N$ чисел, обозначающих время окрашивания и шлифовки для $N$ деталей, упорядочивают по возрастанию;

— если минимальное число в этом упорядоченном списке — это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;

— если минимальное число — это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра;

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

Этот алгоритм применяется последовательно для размещения всех $N$ деталей.

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

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

В первой строке входного файла находится натуральное число $N$ ($N < 1000$) - количество деталей. Следующие $N$ строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания конкретной детали (все числа натуральные, различные).

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

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

5

30 50

100 155

150 170

10 160

120 55

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23208_26.txt

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

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

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

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

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

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

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

5 6

170

200

130

170

110

150

150

180

130

130

200

При таких исходных данных максимальное количество грузов, которое может быть упаковано в контейнеры, равно 4, если взять грузы массой 110, 130, 170 и 170 соответственно. Максимальная разность двух самых тяжёлых грузов в наборе составит 30, если взять грузы массой 110, 130, 170 и 200 соответственно.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/23175_26_2.txt

Во время матча в расширенной версии игры «Морской бой» велась автоматическая фиксация попаданий по игровому полю. Каждое попадание фиксируется по координатам клетки игрового поля (целые положительные числа $x$ и $y$) и времени попадания — целому числу $t$ (в секундах от начала матча).

Игровое поле — прямоугольное. Координаты попаданий $(x, y)$ указываются в формате: $x$ — номер строки (считая сверху вниз, от 1 с шагом 1), $y$ — номер столбца (слева направо, от 1 с шагом 1). Некоторые клетки могли быть поражены несколько раз.

Требуется определить такую клетку, в которую было произведено не менее двух попаданий, и среди них — найти ту, в которой минимальный интервал времени между любыми двумя её попаданиями — наименьший. В ответе нужно вывести сумму координаты этой клетки $(x + y)$, а также этот минимальный интервал в секундах. Если таких клеток несколько, выберите среди них клетку с наименьшим номером строки, а если таких тоже несколько — с наименьшим номером столбца.

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

В первой строке записано одно целое число $N$ — количество попаданий ($1 \leq N \leqslant 1 000 000$). В следующих $N$ строках заданы тройки целых чисел $(x, y, t)$ — координаты клетки и время попадания ($1 \leq x \leqslant 10 000$, $1 \leq y \leqslant 10 000$, $0 \leq t \leq 10^6$).

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

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

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

7

2 3 10

1 1 3

2 3 15

3 2 20

1 1 10

2 3 17

1 1 6

Для приведённого примера более одного попаданий было в клетки с координатами (2, 3) и (1,1). Минимальный интервал между попаданиями, равный двум секундам, был у клетки с координатами (2, 3). Ответ: 5 2.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/22605_26.txt

Исследователь отправляется в экспедицию через пустыню, чтобы добраться до древнего храма, расположенного на расстоянии $R$ километров от стартовой точки (которая определена первым километром). В начале пути его верблюд полностью отдохнувший и может пройти $V$ километров без остановки. По пути расположены оазисы, в которых можно напоить верблюда и позволить ему восстановить силы, чтобы снова пройти до $V$ километров. Известны координаты $N$ оазисов — километры от начала пути, на которых они расположены, а также запас воды в каждом из них (в у. е.). Каждая 1 у.е. воды эквивалентна 1 километру пути, который может преодолеть верблюд.

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

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

В первой строке входного файла находится три натуральных числа: $N$ ($N ≤ 100 000$) – количество оазисов на пути, $R$ ($R ≤ 10 000 000$) - расстояние от стартовой точки до храма, и $V$ ($V < R$) – максимальное количество километров, которые может пройти полностью отдохнувший верблюд. В следующих $N$ строках находятся по два числа: расстояние (в километрах) между стартовой точкой и очередным оазисом, и запас воды в каждом из них (в у. е.). Каждое из чисел целое, не превосходящее 10000000.

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

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

7 50 20

10 20

19 9

15 11

40 20

31 5

41 10

30 10

При таких исходных данных можно сделать 3 остановки: {15, 30, 41} или {15, 30, 40} или {10, 30, 40}. Ответ: 3 40.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/22567_26.txt

Частная клиника работает круглосуточно, в режиме 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.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/22127_26.txt

В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

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

5

43

40

32

40

30

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

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21910_26.txt

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

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

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

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

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

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

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

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

9

40 3

60 33

60 33

50 124

50 126

50 128

40 4

50 72

50 126

Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач через одну (3 задачи). Ответом является пара чисел: 50; 3.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21719_26.txt

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

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

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

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

В первой строке входного файла находится натуральное число $N$ ($N ≤ 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 минуту в предпоследний раз за сутки изменилось число сотрудников.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21598_26.txt

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

Известно, что чем больше номер зоны, тем дальше она расположена от экватора. Из каждой зоны можно попасть только в зоны с большим номером. Имеется $N$ записей, каждая из которых содержит информацию о какой-то зоне: номер текущей зоны, номер переходной зоны, до которой можно добраться отсюда и сумма средств для посещения переходной зоны. Каждая зона может быть представлена в нескольких вариантах с разными переходными пунктами и ценами за переход. Некоторые записи также могут содержать информацию о недостижимых зонах (в которые невозможно попасть, начав движение из зоны №1).

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

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

В первой строке входного файла находится два натуральных числа: $N$ $(N ≤ 100 000)$ – количество записей о зонах и $K$ $(K ≤ 1 000 000)$ - бюджет, которым располагает группа. В каждой из следующих $N$ строк находятся по три числа: номер текущей зоны, номер переходной зоны (в которую можно передвинуться из текущей) и сумма средств, необходимая для перехода. Каждое из чисел натуральное, не превосходящее $1 000 000$.

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

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

8 100

1 4 20

2 4 30

1 3 10

3 4 5

4 5 5

1 2 10

3 5 20

2 5 50

При таких исходных данных можно достигнуть максимум зоны №5 несколькими способами.

Оптимальным вариантом движения будет переход из зоны №1 в зону №3 за 10 ед., затем из зоны №3 в зону №4 за 5 ед. и в конце из зоны №4 в зону №5 за 5 ед. Остаток бюджета при этом составит 80 ед. Ответ: 5 80.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21588_26.txt

В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны меньше длины стороны другой коробки не менее чем на 9 единиц. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

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

5

43

40

32

40

30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», не менее 3 единиц.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21424_26.txt

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.

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

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

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

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

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

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

При таких исходных данных ответом является пара чисел 5 и 6. Условию задачи удовлетворяют места 6 и 7 в ряду 5: перед креслами 6 и 7 нет занятых мест и это первая из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20910_26.txt

На складе есть $K$ стеллажей для хранения грузов. Все стеллажи пронумерованы, начиная с единицы. Каждый стеллаж представляет собой двумерную сетку размером $M * N$, где $M$ — количество рядов, а $N$ — количество полок в каждом ряду. Каждая ячейка стеллажа может хранить только один груз.

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

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

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

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

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

В первой строке входного файла находятся три числа: $K$ — количество стеллажей на складе (натуральное число, не превышающее 1000), $M$ — количество рядов в каждом стеллаже (натуральное число, не превышающее 100) и $N$ — количество полок в каждом ряду (натуральное число, не превышающее 100). Во второй строке находится число $G$ — количество грузов, которые поступят на склад (натуральное число, не превышающее 10000). В следующих $G$ строках находятся два значения: минута поступления груза и минута, в которую груз заберут (все числа неотрицательные, не превышающие 1440).

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

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

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

1 2 2

8

408 1377

1097 1127

225 1349

1085 1332

400 823

100 824

1143 1267

408 1367

При таких входных данных три груза буду размещены в первом ряду, а четыре груза во втором ряду первого стеллажа. Груз 408 1377 не сможет быть размещён на складе. Ответ: 7 1.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20828_26.txt

Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительное 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) - натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов - с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.

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

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

Если полупроходной балл отсутствует, то второе число в ответе должно быть равно нулю.

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

В первой строке входного файла находятся два натуральных числа, не превышающих 10000, через пробел: число $N$ - количество кандидатов и число $K$ - количество мест в отряде. В следующих $N$ строках находятся по 5 чисел через пробел: ID кандидата (натуральное число, не превышающее 100000) и четыре целых неотрицательных числа - сначала результаты испытаний, затем результат собеседования.

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

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

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

6 4

4 80 80 80 0

7 50 80 100 10

11 80 80 70 10

10 100 100 100 2

6 90 90 90 9

2 70 80 80 8

При таких исходных данных рейтинговый список из ID составлен следующим образом: 10 6 7 11 4 2. Два кандидата с баллами 302 и 279 зачислены, проходной балл 279. На оставшиеся два места претендуют три человека, набравшие по 240 баллов, хотя из троих будут зачислены только двое. Таким образом, 240 - полупроходной балл. Ответ: 6 3.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20815_26.txt

Участники викторины письменно отвечают на 10 вопросов различной сложности. За правильный ответ начисляется от 1 до 5 баллов в зависимости от сложности вопроса. За неверный ответ вычитается от 1 до 5 баллов. Участник может не отвечать на какой-то вопрос, в таком случае баллы за этот вопрос не начисляются.

По результатам викторины для каждого участника вычисляются три показателя:

1) сумма – общее количество набранных баллов;

2) плюсы – сумма баллов без учёта неверных ответов;

3) ответы – общее количество сданных ответов (верных и неверных).

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

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

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

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

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

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

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

Первая строка входного файла содержит целое число $N$ ($N ≤ 10 000$) – общее количество участников. Каждая из следующих $N$ строк соответствует одному участнику и содержит 11 целых чисел, разделённых пробелами: сначала ID участника, затем – баллы, полученные им за каждый из 10 вопросов.

Гарантируется, что ID участников не повторяются.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19752_26.txt

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

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

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

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

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

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

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

5

3 50 2 1 4 5

5 40 1 2 3 4

1 37 3 2 4 5

4 25 5 3 1 2

2 50 1 5 4 3

При таких исходных данных выживет только гладиатор под номером 3 и у него останется 39 силы на конец турнира. Ответ: 4 39.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19599_26.txt