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

Скоростной поезд, направляющийся из Москвы в Санкт-Петербург, ожидает пассажиров. Состав поезда включает в себя $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

В супермаркете проводится акция по следующим правилам:

− каждый третий товар ценой больше 350 рублей продается за четверть цены;

− общая цена покупки со скидкой округляется вверх до целого числа рублей;

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

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

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

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

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

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

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

9

10

20

30

360

370

380

390

400

410

В данном случае товары с ценой 10, 20, 30 не участвуют в акции. Остальные 6 товаров покупатель оплатит двумя разными чеками. В первом – 410, 400, 390; во втором – 380, 370, 360. Под акцию попадут товары с ценой 390 и 360. Сумма первого чека: $410 + 400 + 390 * 0.25 = 907.5 = 908$ (магазин округляет вверх), а второго чека: $380 + 370 + 360 * 0.25 = 840$. Итого: $908 + 840 + 10 + 20 + 30 = 1808$. При покупке одним чеком стоимость составит 1823.

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

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

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

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

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

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

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

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

Входной файл содержит заявки на проведение мероприятий в конференц-зале в течение одного дня. В каждой заявке указано время начала и время окончания мероприятия в минутах от начала суток. Если время проведения двух или более мероприятий пересекается, то провести можно не более одного из них. Между окончанием одного мероприятия и началом следующего необходим перерыв не менее 20 минут.

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

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

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

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

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

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

На ленте транспортёра имеется $N$ мест для каждой из $N$ деталей. Места для деталей пронумерованы начиная с единицы.

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

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

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

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

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

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

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

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

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

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

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

5 3

30 50

100 155

150 170

10 160

120 55

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

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

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

Дальнобойщику необходимо добраться до пункта выгрузки товаров, для чего ему предстоит преодолеть путь длиной $R$ километров. В начале пути топливный бак грузовика полон и вмещает в себя такое количество бензина, которого достаточно, чтобы проехать $V$ километров. Имеется информация о количестве заправочных станций на пути и километрах, на которых они расположены. Определите, какое минимальное количество раз придется заправиться дальнобойщику, чтобы достигнуть пункта выгрузки товаров, а также минимально возможный километр, на котором получится заправиться в последний раз.

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

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

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

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

7 50 23

45

15

23

48

29

7

46

При таких исходных данных можно заправиться 2 раза: {7, 29} или {15, 29} или {23, 29} или {23, 46}. Ответ: 2 29.

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

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

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

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

В первой строке файла содержится количество наблюдателей $N$, время начала ЕГЭ – $start$ и время окончания – $end$, то есть время ЕГЭ $[start, end)$. В следующих $N$ строках содержится по два числа $a$, $b$, где $a$ – время начала, $b$ – время окончания работы наблюдателя, то есть наблюдатель работает в промежуток времени $[a, b)$.

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

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

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

5 2 10

1 4

1 3

3 8

7 10

10 11

Ответ: 3 2.

Пояснение: В ответ берутся наблюдатели [1, 4), [3, 8), [7, 10). Время работы первого наблюдателя с начала экзамена $4 - 2 = 2$.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/12478_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/12256_26.txt

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

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

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

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

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

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

2

5

100 200

150 30 60

301 40 1000

170 59 60

40 61 1000

80 1010 1440

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

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

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

Петя играет в компьютерную игру "Кучи камней". Всего в игре есть $N$ уровней. Для каждого уровня известно, какой нужен $skill$ для его прохождения. Кроме того, после прохождения каждого уровня $skill$ Пети увеличивается. Для каждого уровня указано, на сколько увеличится $skill$, после его прохождения. Уровни можно проходить в любом порядке.

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

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

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

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

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

5 6

10 15

8 1

1 2

27 10

9 2

При таких исходных данных Петя сможет пройти четыре уровня:, (10, 15), (8, 1), (1, 2) и (9, 2). Его финальный skill будет равен 26.

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

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

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

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

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

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

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

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

5

6 2

3 1

4 2

12 4

8 2

При таких исходных данных, игроки смогут разместить на ленте максимум 3 шара: (3, 1) -> (6, 2) -> (12, 4). Тогда минимальная конечная отметка ленты для такого размещения шаров будет равна 16.

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

В сеть детских технопарков поступила партия новых роботов. По инструкции каждому роботу рекомендована одна батарейка с достаточной емкостью для каждого робота. Все роботы пронумерованы последовательно от 1 до $N$. Известно, что для каждого робота требуется ровно одна батарейка, емкость которой не меньше $c_{i}$.

Преподавателю робототехники предоставили список из $M$ различных батареек, которые доступны для покупки. Для каждой батарейки известна ее емкость и стоимость. Необходимо определить минимальную сумму покупки батареек для всех роботов и максимальную стоимость одной батарейки, которая будет куплена при оптимальных затратах.

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

Дан входной файл, который в первой строке содержит натуральное число $N$ – количество новых роботов. Затем $N$ строк содержащих целые числа $c_{i}$ – минимальная емкость батарейки для робота с номером $i$. Затем следует натуральное число $M$ – количество видов батареек, предоставленных для закупки. Далее в каждой из $M$ строк содержится пара натуральных чисел $a_{i}$ и $b_{i}$ - емкость батарейки и ее цена соответственно.

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

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

3

1

2

4

5

1 10

1 5

8 6

2 4

4 9

При таких исходных данных минимальная стоимость закупки будет составлять 14 (для первого и второго робота необходимо купить батарейки емкостью 2 и стоимостью 4, а для третьего робота емкостью 8 и стоимостью 6) $4 + 4 + 6 = 14$. Цена самой дорогой купленной батарейки составит 6.

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

Министерство транспорта планирует обновить всё дорожное покрытие на шоссе длиной $R$ километров. Часть работ была проведена ещё в прошлом году, потому дорожники, чтобы не выполнять двойную работу, определили вдоль шоссе отрезки дороги, которые уже отремонтированы, причем информацию о каких-то километрах занесли в реестр несколько раз. Каждый отрезок задаётся километровой меткой старта и конца. Назовём «непригодными» участками шоссе такие непрерывные отрезки, которые не отремонтированы и расположены между отремонтированными участками либо между краем шоссе и ближайшим отремонтированным участком.

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

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

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

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

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

5 50

10 39

15 35

12 25

30 41

45 48

При таких исходных данных три участка являются "непригодными": 1-9, 42-44, 49-50. Длина наибольшего из уже отремонтированных участков равна 31 (10-41). Ответ: 3 31.

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

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

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

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

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

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

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

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

7 3

100 20

200 55

150 50

700 50

50 80

125 88

800 80

При таких исходных данных организация купит товары {125, 88}, {800, 80} и {700, 50} со скидкой. Ответ: 1025 125.

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

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

Проспект длиной $K$ метров освещён $N$ фонарями, стоящими вдоль него. Администрация города выяснила, что количество включённых фонарей избыточно для освещения всего проспекта – какие-то из них можно выключить, чтобы сэкономить на тратах электроэнергии, таким образом, что проспект все равно останется освещён полностью. Входной файл содержит данные о метках начала и конца отрезков, освещаемых фонарями.

Определите, какое максимальное количество фонарей можно выключить так, чтобы проспект остался освещён полностью, а также общее количество фонарей, которые, если их включить, освещают $K$-й метр проспекта.

Примечание. Начало проспекта определено 1-м метром, конец – $K$-м метром.

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

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

Запишите в ответе два числа: максимальное количество фонарей, которые можно выключить, и количество фонарей, которые, если их включить, освещают $K$-й метр проспекта.

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

5 50

1 30

28 50

20 40

1 10

15 50

При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр может быть освещен 2 фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

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

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

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

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

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

В первой строке файла находится натуральное число $N$ – общее количество уроков. В следующих $N$ строках содержатся по два числа – время начала $start$, и время окончания $end$ урока. Длительность урока: $[start, end)$.

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

Выведите два числа – максимальное количество уроков, которые можно посетить и время селфи.

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

4

3 8

1 6

6 9

5 20

Ответ: 2 6.

При таких исходных данных Петя может посетить максимум два урока [1, 6), [6, 9), время селфи – 6.

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

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

Гостевой зал одного из ресторанов города включает в себя $K$ столиков, которые сохранены в базе данных по номерам от 1 до $К$.

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

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

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

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

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

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

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

5

2

130 2 20

150 2 10

570 1 300

180 2 50

600 1 200

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

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

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

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

Каждый заказ обрабатывается в порядке очереди следующим образом:

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

– сбор заказа происходит в течение 2 мин при наличии свободного курьера;

– курьер доставляет заказ до клиента и после выполненного заказа курьер возвращается в пункт сбора заказов;

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

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

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

В первой строке входного файла находится два натуральных числа $K$$(K \leq 1000)$ и $N$$(N \leq 1000)$ – соответственно количество курьеров и количество заказов.

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

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

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

2 5

675 90

716 90

723 72

818 62

1394 45

При таких исходных данных третий и четвёртый заказы будут выполнены с задержкой. Второй заказ будет последним за сутки выполненным заказом без задержки и завершится в 808 мин.

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

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

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

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

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

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

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

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

4

100 200

200 250

400 500

420 480

При таких исходных данных хотя бы один фильм показывался в промежутки времени [100; 250) и [400; 500). Суммарное время равно $(250-100) + (500-400) = 250$. Максимальный непрерывный отрезок времени, в течение которого показывался хотя бы один фильм равен $250-100 = 150$.

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

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

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

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

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

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

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

5

10 150

100 120

131 170

150 180

120 130

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

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

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

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

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

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

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

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

4

14

10

13

13

Ответ для приведённого примера: 4 40.

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

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

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

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

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

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

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

6

10 50

100 150

110 155

120 160

130 170

151 170

При таких исходных данных было два пика посещаемости: в отрезки времени со 130 по 150 минуты и со 151 по 155 минуты. Число посетителей в момент пика посещаемости равно 4.

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

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