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

На производстве штучных изделий $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/9793_26.txt

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

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

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

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

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

5

10 150

100 110

131 170

131 180

120 130

При таких исходных данных можно провести максимум три мероприятия, например, по заявкам 2, 3 и 5. Конференц-зал освободится самое позднее на 180-й минуте, если состоятся мероприятия по заявкам 2, 4, 5.

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

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

Поезд следует по магистрали через $M$ населенных пунктов. Известно, что в поезде $K$ мест. Дан список из $N$ заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на станции $Х$ контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером (от 1 до $K$). При этом сначала осуществляется высадка пассажиров, а затем посадка.

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

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

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

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

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

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

10 3 6

2 6

2 4

3 5

3 8

4 9

4 6

При таких исходных данных добраться до нужного пункта смогут 4 пассажира ( (2, 6), (2, 4), (3, 8), (4, 9) ). При этом свободных мест не будет на перегонах 3 перегонах (3-4, 4-5 и 5-6).

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

В стоматологической клинике работает $K$ специалистов. Все специалисты в базе данных сохранены по номерам от 1 до $K$.

В call-центр стоматологии звонят клиенты, желая записаться на прием ко врачу. В отчете предоставлена информация о звонках, которые происходили последовательно за определенный период времени. Известно время, на которое каждый клиент хочет записаться к специалисту, а также ID-номер специалиста, к которому хочет попасть клиент. При этом, согласно регламенту клиники, длительность любого приема составляет 30 минут. Администратор записывает клиента к специалисту, если на то время, в которое клиент желает пребывать на приёме, не назначено других, ранее сделанных записей. Но если запись к тому специалисту, к которому желает попасть клиент, невозможна, тогда администратор записывает клиента к специалисту с наименьшим ID-номером, среди всех тех, что свободны в рассматриваемое время. Специалисты могут принимать клиентов со следующей минуты после окончания приема предыдущего клиента. Если подходящих специалистов нет, то администратор просит прощения у клиента и сообщает, что он не может записать его.

Длительность рабочего дня стоматологической клиники составляет 840 минут. Последняя минута возможного начала приёма - 810.

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

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

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

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

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

5

2

30 2

50 2

570 1

40 2

150 1

При таких исходных данных первый, второй, третий и пятый клиенты смогут записаться на прием. Последний клиент, которого смогли записать, был записан к первому специалисту. Ответ для примера: 4 1.

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

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

Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.

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

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

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

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

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

2

5

30 60

40 1000

59 60

61 1000

1010 1440

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 6

30 60

61 120

79 160

79 180

100 130

170 1440

При таких исходных данных 1-ый, 2-ой, 3-ий, 4-ый и 6-ой посетители смогут воспользоваться аттракционами. Последний турист сможет прокатиться на первом аттракционе.

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

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

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

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

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

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

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

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

2

5

30 60

40 1110

59 60

61 120

1230 1440

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

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

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

В аэропорту есть камера хранения из $K$ ячеек, которые пронумерованы с 1. Принимаемый багаж кладется в свободную ячейку с минимальным номером. Известно время, когда пассажиры сдают и забирают багаж (в минутах с начала суток). Ячейка доступна для багажа, начиная со следующей минуты, после окончания срока хранения. Если свободных ячеек не находится, то багаж не принимается в камеру хранения.

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

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

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

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

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

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

2

5

30 60

40 60

50 1110

61 1010

1100 1440

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

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

В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы. По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно 13 идущих подряд свободных мест для посадки новых сосен, таких, что непосредственно слева и справа от них в том же ряду растут сосны. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: наибольший номер ряда и наименьший номер места для посадки из числа найденных в этом ряду подходящих последовательностей из 13 свободных мест.

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

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

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

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

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

7

40 3

40 7

60 33

50 125

50 129

50 68

50 72

Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.

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

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

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

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

В первой строке входного файла находится число $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/7096_26.txt

Энтомолог Дмитрий занимается разведением редких видов бабочек. В день из кокона появляется одна особь вида «Павлиноглазка атлас». На выставке Дмитрий может продавать бабочек по различной цене, которая меняется каждый день, так же Дмитрию известна стоимость бабочки ближайшие $N$ дней. Основываясь на известных данных, энтомолог рассчитал максимальное количество монет, которое он может заработать, если считать, что с первого дня у него в запасе была только одна бабочка.

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

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

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

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

5

32

13

85

52

46

При таких исходных данных, ответом будет являться пара чисел 353 255 ($3 * 85 + 52 + 46 = 353$; $3 * 85 = 255$).

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

В супермаркете проводится акция «каждый третий товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по три товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из трёх товаров самый дорогой он поместил на третье место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной. Тогда покупатель разместил товары по-другому.

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

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

Цены товаров указаны в произвольном порядке.

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

Покупатель делит товары на группы наиболее выгодным для себя способом.

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

4

80

30

50

40

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

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

На закупку товаров типов $W$ и $S$ выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров двух типов (по общему количеству). Если можно разными способами купить максимальное количество двух товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа $S$. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.

Определите, сколько будет закуплено товаров типа $S$ и сколько денег останется.

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два целых числа: $N$ - общее количество товаров, и $M$ - сумма выделенных на закупку денег (в рублях). Каждая из следующих $N$ строк содержит целое число (цена товара в рублях) и символ (латинская буква $W$ или $S$), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

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

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

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

Строительная организация возводит два высотных здания, находящихся на расстоянии $M$ друг от друга. Из-за коммунальной аварии потребовалось срочно протянуть трубу от одного здания к другому. В распоряжении организации имеется $N$ труб единичной длины. Известен диаметр каждой трубы. Трубы можно скреплять между собой только при условии, что их диаметр отличается не более чем на 3 единицы.

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

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

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

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

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

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

7 3

2

6

7

8

8

10

15

Для приведённого примера можно составить трассы $6 + 7 + 8, 6 + 8 + 8$, $7 + 8 + 8, 8 + 8 + 10$, максимальная пропускная способность возможна при варианте $8 + 8 + 10$, ответом является пара чисел: 8 10.

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

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

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

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

В первой строке входного файла находится число $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/6056_26.txt

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

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

В первой строке входного файла находится число $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/6031_26.txt

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

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

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

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

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

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

8

50 R

48 G

43 B

40 R

36 B

34 G

22 B

17 R

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

При таких исходных данных условию задачи удовлетворяет набор коробок 50, 43, 34, 22, то есть количество коробок равно 4, а длина стороны самой маленькой коробки 22.

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

В магазине для упаковки подарков есть $N$ кубических коробок и $М$ декоративных замочков к ним ($М < N$). Если длина коробки чётная, то такая коробка красного цвета, если нечётная – синего цвета. Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек, а цвет коробок чередуется. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Замочек подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки. Известно, что коробка, в которой будет находиться подарок, должна быть упакована в синюю коробку.

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

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

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

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

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

6 4

40 36

32 30

30 14

21 21

17

14

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

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

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

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

На складе хранятся кубические контейнеры двух цветов различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Чтобы вложенные контейнеры было лучше видно, их цвета при вложении обязательно должны чередоваться, то есть нельзя вкладывать контейнер в контейнер такого же цвета. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 7 и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Зная размеры и цвета всех контейнеров, определите максимально возможное количество контейнеров в одном блоке и минимальное количество ячеек для хранения всех контейнеров.

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

Каждая строка входного файла содержит натуральное число и букву A или B. Число обозначает размер контейнера в условных единицах, буква – цвет этого контейнера (буквами A и B условно обозначены два цвета).

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

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

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

Известно количество страниц в каждой книге, которую необходимо разместить в шкафу.

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

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

В первой строке входного файла находятся два числа: $N$ – количество книг (натуральное число, не превышающее 5000) и $S$ — максимальное суммарное количество страниц, которое можно разместить на полке (натуральное число, не превышающее $10^{6}$). В следующих $N$ строках находятся по два числа через пробел: значения количества страниц в каждой книге (все числа натуральные, не превышающие 200), и обязательность — значение 0, если книга не является обязательной и 1, если книга является обязательной.

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

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

5 75

10 1

15 1

25 0

20 0

15 0

Для указанных данных ответом будет пара чисел: 3 20.

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

На складе хранятся кубические контейнеры различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 7 и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.

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

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

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

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

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

В магазине имеется $N$ товаров. Известны цена каждого из товаров и его текущий статус (продан или не продан). Товары разделены на две категории - дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает средний чек - $M$. Остальные, соответственно, являются дешёвыми (цена на них не превышает $M$).

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

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

На вход подаётся два числа: $N$ - количество товаров и $M$ - средний чек. Следом $N$ пар чисел. Первое число в паре - цена (она же вид) товара, второе - его статус (0 - не продан; 1 - продан).

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

В ответе укажите два числа.

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

5 60

43 1

90 1

43 0

43 1

90 0

Ответ для примера входных данных: 176 2.

Пояснение к примеру: цена самого популярного дорогого товара = 90 (продан 1 раз), а самого популярного из дешёвых - 43 (продан дважды). Их сумма: $90 + 43*2 = 176$. Продано товаров - 3, всего их в наличии было 5. Осталось: $5 - 3 = 2$. Ответ: 176 2.

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

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

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

В первой строке входного файла находится число $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/4712_26.txt

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

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

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

Цены товаров указаны в произвольном порядке.

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

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

4

80

30

50

40

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

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

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