В кондитерской есть N круглых форм для коржей. Специализация кондитерской – многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 4 единицы меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.
Входные данные
В первой строке входного файла находится число N – количество форм для коржей в кондитерской (натуральное число, не превышающее 10 000). В следующих N строках находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.
Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем – максимально возможный диаметр самого маленького коржа в таком торте.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящих для изготовления многоярусного торта, составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

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

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

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

На кондитерской фабрике имеется N коржей для приготовления тортов, которые накладываются в виде пирамиды. Клиент попросил приготовить на заказ торт-пирамиду максимальной высоты из поставленных друг на друга коржей, такую, чтобы каждый следующий корж имел диаметр не менее чем на 8 единиц меньше, чем предыдущий.
Определите количество коржей, которое необходимо использовать для создания такого торта, и максимально возможный диаметр коржа, который будет находиться на вершине такого торта-пирамиды.
Входные данные
В первой строке входного файла находится число N - количество коржей для приготовления торта (натуральное число, не превышающее 10 000). В следующих N строках находятся значения диаметров коржей (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для сборки необходимого торта, затем максимально возможный диаметр самого маленького коржа в таком торте.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для набора из пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящими для сборки торта-пирамиды, составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а диаметр самого маленького коржа равен 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

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

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

Пример входного файла:
6 5
1 2
2 3
1 2
3 1
3 2

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

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

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит количество песен N (N ≤ 10000). Каждая из следующих N строк содержит три целых числа, записанные через пробел: время начала (T1) и длительность этой песни (T2) (в секундах 0 < T1 ≤ T2 < 300 000 ), а также 1, если песня "любимая" и 0, если "нелюбимая" соответственно.

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

Пример входного файла:

В данном случае наибольшее число песен (4), их временные рамки: (2,3); (3,4); (4,5) или также подходит (4,6); (6,7) , а "нелюбимая" возможная песня, которая играла последней началась в 4, длилась 2, закончилась в 6. Ответ: 4 6

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит количество экпериментов N (N ≤ 10000). Каждая из следующих N строк содержит два целых числа: время начала (T1) и время завершения одного экперимента (T2) (в секундах 0 < T1 ≤ T2 < 5 000 000 ).

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

Пример входного файла:

В данном случае наибольшее число экпериментов (3) выполнялось в интервале времени между 5 и 7. Ответ: 3 2.

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

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

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

В первой строке входного файла находится число N – количество автобусов в текущем расписании (натуральное число, не превышающее 10 000), а во второй строке число 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) работали одновременно.

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

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

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

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

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

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

5
3 7
7 9 4
6
4
1
5
2

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

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

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

Примечание. 1 мебибайт = 2¹⁰ кибибайт = 2²⁰ байт.

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

В первой строке входного файла находится число N – количество файлов (натуральное число, не превышающее 10 000). Во второй строке находятся три числа: 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.

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

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

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

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

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

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

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.

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

(Л. Шастин) Скоростной поезд, направляющийся из Москвы в Санкт-Петербург, ожидает пассажиров. Состав поезда включает в себя K сцепленных пассажирских вагонов, каждый из которых содержит M пассажирских мест. Вагоны и места в них нумеруются от 1 до K и от 1 до M соответственно. Известен перечень, состоящий из N заявок на бронь билетов на поезд за вчерашний день. В каждой из заявок указано время подачи заявки (в минутах от начала суток) и желаемый номер вагона и номер места в нём. Оператор обрабатывает заявки последовательно, начиная с ранее поданных (среди заявок, поданных в одинаковое время, прежде обрабатываются заявки с наименьшими указанными в них номерами вагонов и, если номера вагонов совпали, с наименьшими номерами мест в этих вагонах), и если указанное в заявке место в нужном вагоне ещё свободно, утверждает билет на это место, а иначе утверждает билет на наименьшее по номеру свободное место, расположенное в вагоне, который находится как можно ближе к кабине машиниста (вагон с кабиной машиниста имеет нулевой номер и не является пассажирским). Если же свободных мест нет, билет не утверждается. Определите количество пассажиров, которые получили билет в несоответствии со своей заявкой, а также сумму номеров вагона и места в последнем утвержденном билете.

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

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

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

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

9
10 20
19 30
25 30
30 40
43 48
50 66
70 82
62 65
65 100

При таких исходных данных можно провести максимум пять мероприятий, например, мероприятия по заявкам 1, 3, 4, затем уборка, 6 и 7. Максимально возможное начало самой последней уборки равно 22, если выбрать мероприятия в следующем порядке: 1, 3, 4, уборка с 40 минуты по 62, 8 и 9.

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

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

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

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

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

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

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

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

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

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

5
20 120
90 20
147 43
150 30
120 20

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

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

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

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

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

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

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

7 5
33 34
39 35
37 37
35 30
30 36
35
34

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

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

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

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

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

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

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

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

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

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

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

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

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.

(C. Горбачёв) На заводе изготовлены N деталей. Для каждой детали известна её длина. В хранилище имеется K мест. Места в хранилище пронумерованы слева направо, начиная с единицы. Детали в хранилище располагают по следующему правилу:
— все N деталей упорядочивают по возрастанию их длины;
— детали с четными длинами располагают в левой части хранилища, с нечетными - в правой.
Этот алгоритм применяется последовательно для размещения K деталей.
Определите номер позиции в хранилище, на которой будет расположена последняя деталь, и сумму нечетных длин деталей, которые
будут расположены правее неё.

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

Типовой пример организации данных во входном файле:
5 4
30
15
22
11
121

При таких исходных данных последней займёт своё место деталь с длиной 30. Она займёт второе место, сумма деталей с нечетными длинами в хранилище составит 26.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

• все 2N чисел, обозначающих время окрашивания и шлифовки для 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.

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