Банк заданий
ЕГЭ по информатике Задание №26 Обработка данных с помощью сортировки, Задания на обработку данных с помощью сортировки

В волшебном зимнем королевстве, где снежные феи дарят знания, студенты сдают важные экзамены в Академии Снежных Искусств. Каждый студент проходит четыре испытания, за каждое из которых можно получить от 1 до 6 магических баллов. Однако, если студент получает хотя бы одну "единицу", он считается не сдавшим и не может стать настоящим магом.

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

Студенты, не сдавшие экзамены, сортируются следующим образом: сначала идут те, кто получил одну "единицу", затем те, у кого две "единицы", потом те, кто получил три "единицы", и наконец, те, кто получил "единицы" за все четыре экзамена. Если у студентов одинаковое количество "единиц", их ID располагаются в порядке возрастания.

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

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

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

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

Гарантируется, что общее число студентов $N$ кратно 5 и хотя бы один студент имеет более одной "единицы". Во входном файле все ID различны.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На престижном турнире по пауэрлифтингу $M$ тяжелоатлетов соревнуются в силе, поднимая гирю. Спортсмены поочередно подходят к стойке и выбирают вес для дальнейшего подъема. Каждый из них знает свои возможности и, стремясь к победе, выбирает один максимально возможный вес, который способен поднять, из предложенного на мероприятии набора из $N$ разновесных снарядов.

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

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

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

Первая строка содержит два целых числа: $N$ — количество доступных снарядов и $M$ — количество атлетов ($1 ≤ N ≤ 50 000$, $1 ≤ M ≤ 50 000$). Следующие $N$ строк содержат по одному целому числу — веса снарядов (от 1 до 100000). Последние $M$ строк содержат по одному целому числу — максимальные веса, которые могут поднять атлеты (от 1 до 100000).

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

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

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

3 3

50

100

70

60

80

65

При таких исходных данных первый и третий атлеты выберут вес 50, так как они не могут поднять 70 и 100. Второй атлет выберет вес 70, так как он не может поднять 100. Средний вес: $(50 + 50 + 70) / 3 = 56$. Чаще всего выбирали снаряд с весом 50. Ответ: 56 50.

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

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

Инженер станции анализирует данные, чтобы определить пики загруженности — это промежутки времени, когда на платформе находилось наибольшее количество поездов. Такие периоды могут повторяться в течение суток.

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

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

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

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

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

Пример входных данных

5

12 140 250

44 200 278

13 0 41

84 250 310

11 13 190

Для таких входных данных пиковое количество поездов равно 2, а количество таких пиков — 3 (с 13 до 41 минуты, с 140 до 190 и с 200 до 278). Самый длинный пик — третий, сумма номеров поездов для него равна $12 + 44 + 84 = 140$ . Ответ: 3140.

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

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

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

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

В первой строке входного файла находятся два числа: $N$ (натуральное число, не превышающее $10^{5}$) — количество балок, доступных для покупки, и $R$ (натуральное число, не превышающее $10^{10}$) — длина одной платформы (в у.е). В каждой из следующих $N$ строк находятся размеры соответствующей балки, разделенные друг от друга одним пробелом. Каждая балка может иметь разное количество размеров (от 1 до 15). Все размеры представлены натуральными числами, не превышающими $10^{7}$. Информация о каждой балке записана на отдельной строке.

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

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

5 63

20 15 30

10 5 14 9 11

40 8

7

50 7 12 9 16 35

Пример входного файла приведён для набора из 5 балок.

При таких исходных данных для построения платформ нужной длины по двум сторонам можно купить балку №1 в размере 30 у.е., балку №3 в размере 40 у.е, балку №5 в размере 50 у.е. и напоследок любую балку из доступных, но наименьший подходящий размер в 7 у.е. будет иметь балка №4. Ответ: 4 4.

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

На общегородском учебном совете было принято решение организовать поход классов на премьеру нового полнометражного фильма-триллера «ЭГЕ». Для недопущения массовых беспорядков было решено, что на один сеанс могут попасть ученики только одной параллели одной школы. Также нельзя разбивать одну параллель на несколько сеансов. Порядок, в котором школы и классы выбирают сеанс, строго регламентирован важной коллегией: приоритет отдаётся ученикам более старших классов (то есть сначала выбирают сеанс для учеников 11 класса, затем 10, затем 9 и т.д.) в порядке возрастания номеров школ. По известному количеству сеансов фильма и свободных мест для каждого сеанса определите, какое наибольшее количество параллелей смогут «насладиться» этим шедевром, а также количество учеников, которые увидят этот фильм.

В ответе запишите два целых числа — сначала количество классов, затем количество учеников в этих классах.

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

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

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

Два натуральных числа: искомое количество параллелей и количество учеников в них.

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

3 2

15 10 22

899 11 35

44 3 25

27

26

При таких исходных данных на сеанс смогут пойти два класса: 10 класс (22 человека) из школы №15 и 3 класс (25 человек) из школы №44. Ответ: 2 47.

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

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

1) На бюджетные места поступают ученики с наибольшей суммой баллов по трём предметам с учетом балла за олимпиаду.

2) Если несколько учеников набрали одинаковую сумму баллов, то в приоритете те, кто набрал больший балл по информатике.

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

База данных представляет из себя следующие поля: ID ученика, балл по информатике, балл по математике, балл по русскому, балл олимпиады.

В ВУЗЕ мечты 300 бюджетных мест. Определите ID ученика, который последний поступает на бюджет и наибольший ID, который не прошел на бюджет но набрал по информатике столько, сколько последний поступивший.

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

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

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

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

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

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

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

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

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

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

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

8

2

9

8

4

12

2

10

3

Пример входного файла приведён для набора из восьми игральных карт. При таких исходных данных идеальный карточный домик будет состоять из трёх уровней: {4, 8, 9}, {3, 2}, {2}. Сумма номеров карт, из которых состоит этот домик, равна 28. Ответ: 3 28.

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

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

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

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

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

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

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

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

5 20

20000

8000

9000

12000

5000

При таких исходных данных продавец погрузит арбузы весом 12 и 8 кг. Ответ: 2 8000.

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

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

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

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

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

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

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

4

80

50

30

40

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

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

Отбор кандидатов в матросы происходит по сумме баллов трех экзаменов. На заранее известное количество мест отбираются кандидаты, набравшие большую сумму баллов по результатам трех экзаменов. Все кандидаты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом. Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование, а при равенстве баллов за собеседование – приоритет имеют кандидаты с наименьшими ID.

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

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

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

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

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

6 3

1 90 90 90 10

3 60 70 80 8

5 63 60 90 6

8 50 80 100 4

4 40 95 80 7

11 80 63 72 6

При таких входных данных проходной балл равен 230, полупроходной 215, на оставшееся одно место будет назначен кандидат, набравший в сумме 215 баллов и получивший по собеседованию 7 баллов. Ответ для приведённого примера: 8 2.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/17565_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 и 8. Условию задачи удовлетворяют места 7 и 8 в ряду 5: перед креслами 7 и 8 нет занятых мест и это последняя из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.

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

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

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

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

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

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

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

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

100 4

80

30

50

40

При таких исходных данных можно перевезти максимум 2 посылки.

Их возможные объёмы: 30 и 40, 30 и 50 или 40 и 50. Наибольший объём посылки из перечисленных пар - 50, поэтому ответ для приведённого примера: 2; 50.

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

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

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

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

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

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

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

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

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

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

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

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

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

На кондитерской фабрике имеется $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/15341_26.txt

На олимпиаде по программированию задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая $i$-я задача ($1 ≤ i ≤ n$) становится доступной участникам в свой момент времени $s_{i}$. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть $t_{i}$ минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение каждой задачи участник получает k баллов.

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

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

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

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

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

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

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

6 5

1 2

2 3

1 2

3 1

3 2

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

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

Известно расписание движения автобусов одного из районов некоторого густонаселенного города за 2023 год, составленное с опорой на то, что в любом месяце ровно 30 дней. Транспортные логисты называют "прайм-таймом" такой отрезок времени, в каждую минуту которого работают хотя бы K автобусов, но при этом в минуту до начала отрезка и в минуту после конца отрезка работает меньше $K$ автобусов. Причём считается, что в первую минуту (в точке начала отрезка) и в последнюю минуту (в точке конца отрезка) автобус все ещё работает. Специалисты владеют данными об отрезках времени, задающих время начала и конца непрерывной работы соответствующего автобуса. Данные о времени представлены в формате D.M.H.T (минута T часа H дня D месяца M). По имеющимся данным определите количество "прайм-таймов", а также наибольшее число автобусов, работавших одновременно в какую-либо минуту.

Примечание. Например, запись 20.03.16.57 отождествляет дату и время: 20 марта, 16:57.

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

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

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

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

5

2

14.04.17.31 30.10.19.31

03.03.09.18 07.03.22.15

01.01.00.00 27.05.18.25

23.09.17.46 30.12.23.57

21.08.15.11 30.12.21.18

При таких исходных данных число "прайм-таймов" равно трём, и при этом максимум три автобуса (№1, 2 и 3) работали одновременно.

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

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

Группа исследователей отправляется на экспедицию в горы, где им нужно распределить свои припасы по нескольким хранилищам. У них есть $N$ разновесных пакетов с продуктами, которые им нужно разместить в $K$ пещерах, каждая из которых может вместить до $M$ кг продуктов. Исследователи начинают последовательно заполнять пещеры по возрастанию их номеров: они помещают в каждую следующую пещеру сначала самый тяжелый из оставшихся пакетов, затем самый легкий, а потом снова самый тяжелый – и так поочередно до тех пор, пока в пещеру влезает следующий подходящий пакет.

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

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

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

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

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

5

3 7

7 9 4

6

4

1

5

2

При таких исходных данных пещеры с номерами 4 и 7 будут заполнены до отвала (6 + 1) и (5 + 2), а в последней пещере с номером 9 останется 3 кг свободного места (в неё погрузят последний пакет с весом 4 кг). Ответ: 9 3.

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

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

Игроман по имени Иван обожает проводить время за компьютерными играми, но объем SSD-накопителя, установленного на его любимом ноутбуке, не безграничен. Иван-игроман хочет насладиться очередным шедевром индустрии видеоигр, для установки которого требуется освободить на SSD-накопителе хотя бы $M$ мебибайт памяти. Для этого Иван-игроман подготовил список файлов, которые можно удалить для очистки свободного места на диске. Собранные Иваном метаданные характеризуют тип (он определяется номером от 1 до $K$) и объем каждого из файлов (выраженный в байтах – b, кибибайтах – kb или мебибайтах – mb).

Известно, что можно удалить не более $R$ файлов каждого из $K$ типов. Определите минимальное количество файлов, которые можно удалить так, чтобы освободить хотя бы $M$ мебибайт памяти, а также наименьший возможный объем (в байтах) удаленного при этих условия файла.

Примечание. 1 мебибайт = $2^{10}$ байт, кибибайт = $2^{20}$ байт.

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

В первой строке входного файла находится число $N$ – количество файлов (натуральное число, не превышающее 10000). Во второй строке находятся три числа: $K$ – количество типов файлов, $R$ – наибольшее количество файлов одного типа, которые можно удалить, и $M$ – минимальный объем памяти (в мебибайтах), который нужно освободить ($R < K < M < 1 000 000$). В следующих $N$ строках находятся три значения – тип текущего файла, его объем и единица измерения объема (b / kb / mb).

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

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

7

2 2 600

1 250 mb

2 40 mb

1 102400 kb

1 150 mb

2 204800 kb

2 26214400 b

1 170 mb

При таких исходных данных можно удалить 2 файла типа №1 (250 mb + 170 mb или 250 mb + 150 mb) и 1 файл типа №2 (204800 kb). Минимальный возможный объем удаленного при таких условиях файла = 150 mb = 157286400 b. Ответ: 3 157286400.

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

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

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

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

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

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

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

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

6

2 70 2

2 25

1 10

1 15

2 20

1 5

1 8

При таких исходных данных будут закуплены 2 детали вида №2 (25 + 20) и 3 детали вида №1 (10 + 5 + 8). Ответ: 5 3.

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

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

Скоростной поезд, направляющийся из Москвы в Санкт-Петербург, ожидает пассажиров. Состав поезда включает в себя $K$ сцепленных пассажирских вагонов, каждый из которых содержит $M$ пассажирских мест. Вагоны и места в них нумеруются от 1 до $K$ и от 1 до $M$ соответственно.

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

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

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

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

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

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

2

2

7

1010 1 2

440 2 1

890 2 1

310 1 2

170 2 2

540 1 2

1390 2 1

При таких исходных данных билеты без изменений будут утверждены по заявкам №2, 4 и 5. Последний утвержденный билет по заявке №6 будет не соответствовать заявке (он будет определен на место №1 в вагоне №1, т.к. место №2 в вагоне №1 уже занято). Ответ: 1 2.

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

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

Четыре подружки решили сходить в кинотеатр на премьеру фильма "Сосны 35. Точно последние". На сайте они нашли информацию о местах, которые были зарезервированы зрителями. Девушки хотят купить билеты таким образом, чтобы иметь возможность сесть рядом, а места перед ними в соседнем ряду были свободны.

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

Примечание. Номера мест и рядов в кинотеатре нумеруются последовательно, начиная с 1. Ближе всего к экрану расположен ряд номер 1.

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

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

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

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

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

6 5 6

3 6

5 1

5 4

4 1

2 2

1 3

При таких входных данных подружки могут купить билеты на 2, 3, 4 и 5 места в 4 ряду. Ответ 4 2.

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

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

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

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

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

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

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

5

20 120

90 20

147 43

150 30

120 20

При таких исходных данных можно провести максимум три поединка, например, по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними поединками составит 10 мин., если состоятся поединки по заявкам 2, 4 и 5.

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

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

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

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

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

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

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

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

7 5

33 34

39 35

37 37

35 30

30 36

35

34

Ответ для примера: 2 30.

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

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