ЗАДАНИЕ 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.

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

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

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

В первой строке файла содержится количество наблюдателей 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.

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

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

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

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

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

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

100 4
80
30
50
40

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

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

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

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

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

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

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

6
43
40
33
28
40
29

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

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 29, 40 и 43 или 33, 40 и 43 или 28, 33, 40, 43 соответственно, т.е. наибольшее количество коробок равно 4, а наибольшая длина стороны самой маленькой коробки равна 28.

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

(PRO100 ЕГЭ) Петя играет в компьютерную игру "Кучи камней". Всего в игре есть 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.

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

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

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

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

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

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

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

5

6 2

3 1

4 2

12 4

8 2

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

(И.Карпачев) В сеть детских технопарков поступила партия новых роботов. По инструкции каждому роботу рекомендована одна батарейка с достаточной емкостью для каждого робота. Все роботы пронумерованы последовательно от 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. 

(Л. Шастин) Министерство транспорта планирует обновить всё дорожное покрытие на шоссе длиной 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.

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

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

Входные данные
В первой строке входного файла находится два натуральных числа: N (N ≤ 10 000) – количество товаров у поставщика и K (K < N) – количество товаров, на которые магазин готов сделать скидку. Следующие N строк содержат пары чисел, обозначающих стоимость товара и размер возможной скидки в процентах (от 0 до 100). Каждое из чисел целое, не превосходящее 1 000 000. 
Запишите в ответе два числа: сумму, которую заплатит организация за 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.

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

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

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

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

Типовой пример организации данных во входном файле
5 50
1 30
28 50
20 40
1 10
15 50
При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр может быть освещен 2 фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

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

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

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

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

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

Типовой пример организации данных во входном файле
4
3 8
1 6
6 9
5 20

Ответ: 2 6.

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

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

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

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

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

В первой строке входного файла находится два натуральных числа K (K ≤ 1000) и N (N ≤ 1000) – соответственно количество курьеров и количество заказов.
Каждая из следующих N строк содержит два натуральных числа: указанное в заявке время создания (в минутах от начала суток) и необходимое время для доставки соответствующего заказа, каждое из которых не превышает 1440.
Запишите в ответе два числа: количество заказов, выполненные с задержкой, и минута завершения последнего за сутки заказа, выполенный без задержки.
Типовой пример организации данных во входном файле
2 5
675 90
716 90
723 72
818 62
1394 45
При таких исходных данных третий и четвёртый заказы будут выполнены с задержкой. Второй заказ будет последним за сутки выполненным заказом без задержки и завершится в 808 мин.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440. 
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

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

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

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

6
10 50
100 150
110 155
120 160
130 170
151 170

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

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

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

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

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

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

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

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

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

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

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

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

5
30 50
100 155
150 170
10 160
120 55

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

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

Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время
окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то
провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести
можно оба. Определите максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время
окончания последнего мероприятия.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение мероприятий. 
Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия (в минутах от начала суток).
Типовой пример организации данных во входном файле
5
10 150
100 110
131 170
131 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, по заявкам 2, 3 и 5. Конференц-зал освободится самое позднее на 180-й минуте, если состоятся мероприятия по заявкам 2, 4, 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

На въезде в город оборудована сельскохозяйственная ярмарка. Лотки для продажи стоят с двух сторон дороги с двусторонним движением. С каждой стороны расположено по K мест для торговли. Место бронируется на определенное количество минут, при этом управляющим ярмарки закладывается 15 минут на освобождение места после окончания его аренды. Места, которые расположены вдоль полосы по направлению в город, считаются наиболее прибыльными, поэтому при возможности занимаются в первую очередь. Если свободных мест нет, но новый продавец видит, что на одном из мест предыдущий продавец собирает вещи, то он встает в очередь за ним. При этом он не отличает сколько времени осталось на сбор, если несколько продавцов освобождают свое место. Поэтому встает в очередь за первым по номеру лотка. В случае, когда по направлению в город нет свободных мест, но есть места по направлению из города, продавец выбирает подождать собирающегося продавца с «прибыльной» стороны, если таковые имеются. Если на желаемое время мест нет и ни один из продавцов не собирается, то новый продавец уезжает с ярмарки.
В случае, когда на одно и тоже время претендует несколько продавцов, управляющий делает выбор в пользу продавца, который собирается арендовать место на большее время.
Определите, сколько продавцов смогут занять места, и сколько минут за обозначенный период будут заняты все места по направлению в город (с учетом времени на сборы).

Входные данные:
В первой строке файла содержится два числа K (1 ≤ K ≤ 500) – количество мест на каждой из сторон дороги и N (1 ≤ N ≤ 10000) – количество потенциальных продавцов.
В каждой из N следующих строк содержится два числа: T (1 ≤ T ≤ 4200) – время от начала ярмарки в минутах, когда продавец планирует начать торговлю, и P (1 ≤ P ≤ 300) – желаемое время аренды лотка.

Выходные данные:
Два числа: количество продавцов, которые смогут занять место, и суммарную длительность аренды всех лотков вдоль стороны дороги по направлению в город.
 
Пример входных данных:
2 6
1 10
11 25
16 15
21 25
26 20
31 10

Обозначим лотки, как 1В и 2В (выгодный) со стороны в город, и 1Н, 2Н (невыгодный) – из города.
Тогда
1 продавец: 1В – 1-10 минут + 15 минут на сборы  (лоток занят с 1 по 25 минуты)
2 продавец: 2В – 11-35 минут + 15 минут на сборы (лоток занят с 11 по 50 минуты)
3 продавец: 1В – дождаться, пока соберется предыдущий, 26-40 + 15 минут на сборы (лоток занят с 26 по 55 минуты)
4 продавец: 1Н – 21-45 + 15 минут на сборы (лоток занят с 21 по 60 минуты)
5 продавец: 2Н – 26-45 + 15 минут на сборы (лоток занят с 26 по 60 минуты)
6 продавец уезжает с ярмарки

При этом все места с выгодной стороны будут заняты 40 минут (с 11 до 50).

Графически (с сеткой в 5 минут) можно представить работу ярмарки при таких входных данных следующим образом, где зеленый цвет – время торговли, желтый – время сборов:

Поезд следует по магистрали через M населенных пунктов. Известно, что в поезде K мест. Дан список из N заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на станции Х контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером (от 1 до K). При этом сначала осуществляется высадка пассажиров, а затем посадка. 
Определите, сколько пассажиров смогут добраться до пункта своего назначения и сколько перегонов будут заняты все места поезда (перегон – участок магистрали между соседними населенными пунктами).
Входные данные:
В первой строке файла задано три числа: M (2 ≤ M ≤ 2000) – количество населенных пунктов со станциями на магистрали, K (1 ≤ K ≤ 1000) – количество мест в поезде и N (1 ≤ N ≤ 10000) – количество пассажиров, желающих проехать на поезде.
В каждой из последующих N строк располагаются пары чисел: сначала номер населенного пункта, откуда хочет начать свою поездку пассажир, затем номер населенного пункта, где пассажир собирается сойти с поезда.
Выходные данные:
Два числа: сначала количество пассажиров, которые смогут добраться до нужной им станции, затем количество перегонов, при прохождении которых в поезде будут заняты все места.
Пример входных данных:
10 3 6
2 6
2 4
3 5
3 8
4 9
4 6
При таких исходных данных добраться до нужного пункта смогут 4 пассажира ( (2, 6), (2, 4), (3, 8), (4, 9) ). При этом свободных мест не будет на перегонах 3 перегонах (3-4, 4-5 и 5-6). 

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

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

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

Пример:
3 5
1 10 1 2
4 10 1 3
7 10 2 3
19 5 3 1
20 8 2 1
Всего 3 парковки и 5 заявок. На начало эксперимента на 1ю нужно подвезти 2 самоката, на 2ю один, на 3ю к моменту старта 4го уже приедет самокат с 1й. Поэтому там 0шт на начальный момент. И в конце последний самокат заберут со 2й. Всего 3шт хватит всем. А пик будет на 7й минуте - 3 самоката в аренде. Ответ 3 3

(Е. Джобс) На стадионе есть система предварительных заявок на покупку билетов на футбольный матч. Каждая заявка содержит одно число – количество билетов, которые желает выкупить клиент. 
Утром перед матчем оператор распределяет заявки по следующему алгоритму:
1)    Все билеты в одной заявке должны быть в одном ряду,
2)    В первую очередь подтверждаются заявки с наибольшим количеством забронированных мест,
3)    Места проверяются в порядке следования рядов, то есть оператор старается разместить все места из заявки в ряд с наименьшим номером. При этом максимально близко к началу ряда.
Определите, сколько заявок подтвердит оператор и сколько свободных мест останется на стадионе после распределения всех заявок по описанному алгоритму.
Описание входных данных:
В первой строке находится три числа: количество рядов на стадионе K, количество мест в одном ряду M и количество заявок N. В каждой из N следующих строк находится одно число – количество билетов в заявке.
Описание выходных данных:
Два числа – сначала количество подтвержденных заявок, затем количество оставшихся на стадионе мест.

Пример входных данных:
3 20 7
8
15
10
17
13
6
4

Для таких данных оператор удовлетворит 5 заявок – 15, 17, 13, 6 и 4. На стадионе останется 5 свободных мест.

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

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

Выходные данные
Два целых неотрицательных числа: наибольший номер ряда, в котором есть хотя бы одно удобное место, и общее количество удобных мест.
Пример входных данных:
11
5 1
20 30
5 7
20 18
5 30
20 1
20 4
20 16
5 13
20 10
20 24

В этом примере подходят ряд 5, где слева и справа от 7 места есть ровно по 5 свободных мест, и ряд 20, где подходят 10-е и 24-е места. В ответ пойдёт ряд с наибольшим номером, содержащий удобные места, и общее количество удобных мест. Ответ: 20 3.

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

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

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

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

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

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

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

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

5
2
30 2
50 2
570 1
40 2
150 1

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

Ответ для примера: 4 1.

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

(Л. Шастин) На склад магазина привезли N упаковок свежей продукции. Вновь привезенную продукцию сортируют по K холодильным камерам, вместимость каждой из которых равна M кг. Холодильные камеры, в свою очередь, пронумерованы от 1 до K. Фасовщики заполняют холодильные камеры последовательно, начиная с 1-й. Сначала погружают товары наибольшего объема (до тех пор, пока самый большой из оставшихся товаров влезает в холодильную камеру), стремясь заполнить текущую холодильную камеру до предела, а оставшееся свободное место начиняют товарами наименьшего объема. Гарантируется, что K камер хранения достаточно для сортировки всей продукции по описанной выше стратегии.

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

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

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

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

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

5
5
10
9
7
6
4
1

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

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

(В. Рыбальченко)Рядом с жилым домом есть платная парковка, состоящая из трех уровней. На каждом уровне по К парковочных мест. Стоимость парковки за час на первом уровне равна С, на втором 2С, на третьем 4С. За день на парковку приезжает N машин (гарантируется, что все машины приехали в разное время). Записи, когда приехал клиент идут в случайном порядке. Водитель выбирает один из трех уровней, покупает целое количество часов и занимает первое свободное место в тот же момент, как приехал. Место считается свободным через минуту, после того как водитель планировал уехать. Если все места заняты – клиент уезжает. Необходимо определить сколько владелец парковки заработает за день и сколько клиентов получится обслужить. 

Входные данные
На первой строке одно число N – количество клиентов, приехавших за день. На второй строке одно число K – количество парковочных мест на каждом уровне. На третье строке одно число С – стоимость парковки на первом уровне. Далее N строк, в каждой из которых указано время, когда клиент приехал, время, когда он планирует уехать (дано в секундах от начала дня) и уровень парковки, который водитель хочет выбрать.

Типовой пример организации данных:
6
1
10
10 3600 1
1500 3600 2
3650 7100 1
8100 8200 3
3660 9000 2
4000 5000 1
При таких данных встать на парковку смогут первый, второй, четвертый, пятый и шестой клиенты. Ответ 120 5

На парковке имеется 70 мест для легковых автомобилей и 30 мест для микроавтобусов. Приезжающий на парковку автомобиль занимает любое свободное место соответствующего типа. При этом если свободных мест для легковых автомобилей нет, то легковой автомобиль занимает свободное место, предназначенное для микроавтобуса, но микроавтобус не может занять место, предназначенное для легкового автомобиля. Если подходящего места нет, автомобиль уезжает.
Входные данные
Первая строка входного файла содержит целое число N – общее количество автомобилей, в течение суток приехавших на парковку. Каждая из следующих N строк описывает один автомобиль и содержит 2 целых числа и букву. Первое число означает время в минутах с начала суток, когда автомобиль прибыл на парковку, второе – необходимую длительность стоянки в минутах. Буква означает тип автомобиля: A – легковой, B – микроавтобус.
Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему по типу.
В ответе запишите два целых числа: сначала количество микроавтобусов, которые смогут припарковаться, затем – общее количество автомобилей (как легковых, так и микроавтобусов), которые уедут из-за отсутствия мест.

(А.Богданов) Отель расположен на берегу моря и состоит из небольших домиков, расположенных линиями от моря по К домов в линию. Первая линия домиков расположена на берегу. Перед сезоном все домики подготовлены к заселению. Все заявки на заселение записываются в журнал по мере поступления. В каждой заявке указан час заезда и час выезда, от начала сезона. Домик считается свободным в следующий час после выезда. Домик для заселения выбирается в момент приезда. Турист всегда заселяется в ближайший к морю домик. Если в линии свободных домиков несколько, то в первый слева. Определить максимальный номер линии, в которой будет заселяться хотя бы один домик и количество заселенных домиков в следующий час после последнего заселения.

Входные данные: Журнал заявок. В первой строке два числа K и N. Далее N строк по два числа: час заезда и час выезда

Пример:
3 5
7 65 
10 40 
16 33
35 55
39 46
В линии по три домика. В первый день будут заселены три домика первой линии. На следующий день заселят дом на 2й линии. После 39ч в отеле будет занято 4 домика. Ответ: (2,4)

(М. Шагитов) В течение дня в магазине электроники каждые t минут, начиная с момента t, предлагается один товар со скидкой. В течение дня магазин посещает N клиентов, желающих приобрести товар со скидкой (по скидочной карте). Известны время прихода и ухода каждого клиента, а также число товаров, уже приобретенных ранее с использованием скидочной карты. Клиент может купить товар со скидкой, если он присутствует в магазине в момент начала продажи товара и он купил ранее по скидочной карте менее, чем M товаров. В случае, когда несколько клиентов могут купить товар, выбирается тот, кто до этого купил по скидочной карте меньше товаров. При равенстве количества товаров, преимущество получает тот, кто уходит позже. После покупки число купленных товаров на скидочной карте клиента увеличивается на один. На последней минуте, когда покупатель уходит из магазина, он также может купить скидочный товар.

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

Входные данные представлены в файле следующим образом. Первая строка содержит три натуральных числа: t (1 ≤ t ≤ 1440) - интервал между продажами товаров, N (1 ≤ N ≤ 1000) – количество покупателей, и M (1 ≤ M ≤ 10^{9}) – ограничение для скидки. В следующих N строках указаны три значения: минута прихода покупателя в магазин, минута ухода покупателя из магазина (натуральные числа, не превышающие 1440) и количество товаров, купленных ранее по скидочной карте (натуральное число, не превышающее 10^{9}).

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

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

10 5 4
5 50 3
1 30 2
10 56 1
4 40 3
20 40 2

При таких исходных данных товары для пришедших покупателей продавались в единственном экземпляре в минуты: 10, 20, 30, 40, 50. В итоге покупатель
{10, 56, 1
} купил наибольшее количество товаров – 3 (на минутах 10, 20 и 40) и находился в магазине 47 минут (с 10 по 56-ю минуту). Покупатели
{20, 40, 2
} и
{5, 50, 3
} купили только один товар каждый (на минутах 30 и 50 соответственно), а остальные покупатели не смогли ничего приобрести. Ответ: 47  3.

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

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

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

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

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

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

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

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

2
5
30 30
40 60
59 1
61 59
1230 25

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

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

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

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

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

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

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

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

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

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

10
5
30 60 5
40 1110 2
30 60 3
60 120 1
120 1440 2

При таких исходных данных первая, вторая, третья и пятая группа туристов смогут заселиться в номера. В первые 29 минут от начала дня все номера были свободны, далее до 40 минуты были свободны 2 номера. С 40-й и до 60-й минуты все номера были заняты на протяжении 21-й минуты, а затем до конца дня хотя бы один из номеров всегда был свободен. Значит, суммарное время, в которое хотя бы один из номеров был свободен, равно 1440 - (60 - 40 + 1) = 1440 - 21 = 1419. Ответ: 4 1419.

(А.Богданов) В гостинице составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и пронумерованы с 1 до К. В основе плана журнал заявок, в каждой из которых записано время заезда и время выезда для N заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению.

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

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

Входные данные: На первой строке одно число K – количество номеров. На второй строке одно число N – количество заявок. Далее N строк, в каждой из которых указано время заезда и время выезда в минутах, начиная с 0:00 воскресенья.

Пример на маленьких числах:

2 # кол-во номеров К
5 # кол-во заявок N
10 30 # сразу заезжает в №2
15 40 # сразу заезжает в №1
40 80 # ждет 21 минуту и заезжает в №2
55 90 # ждет 16 минут и заезжает в №1
76 180 # ждет 35 минут и заезжает в №2

Для приведенного примера в ответ нужно записать 35 минут ожидания и 2й номер, заселенный последним

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

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

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

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

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

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

2 6
30 60
61 120
79 160
79 180
100 130
170 1440

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

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

(А. Кирпичев) Начинающий программист Григорий работает на бирже труда. Он способен выполнять неограниченное количество задач одновременно. У него имеется информация о заказах на бирже труда за день: время появления заказа на бирже (в минутах от начала дня), время, которое Григорий потратит на его выполнение (также в минутах), сколько работодатель платит за этот заказ (в дублях). Кроме того, ему известно, что, если он не берет заказ в ту же минуту, в которую он появляется на бирже, заказ забирает конкурент Григория. Григорий знает, что профессиональные программисты получают 300 000 дублей в наносекунду, и хочет получить эту сумму хотя бы за день. Найдите, какое минимальное количество заказов Григорий должен принять, чтобы добиться своей цели, какое максимальное количество заказов Григорию придется выполнять одновременно при том, что Григорий придерживается стратегии, в которой он берет заказы с максимальной стоимостью, но делая это максимально эффективно: если у него есть выбор между вариантами с одинаковой зарплатой (и все он взять не может), он предпочтет тот, при котором он будет работать над меньшим числом задач одновременно

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

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

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

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

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

6                            

100       200       500

300       50          300

250       5            100

3            57          20

65          30          30

200       150       150

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

При таких условиях Григорий возьмет задачу за 500 (1), за 300 (2), за 150 (6) и за 100 (3), чтобы в сумме получить 1000 рублей (Григорий берет заказы с максимальной стоимостью), а значит он будет работать в период 100-199 над одной задачей (1), 200-249 над двумя задачами (1 и 6), 250-254 над тремя задачами (1, 3 и 6), 255-299 над двумя задачами (1 и 6), 300-349 он продолжает работать над двумя задачами (2 и 6). Пиковая нагрузка Григория была во время 250-255, когда он работал на тремя задачами сразу. Поэтому ответ для приведенного примера: 4 3.

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

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

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

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

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

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

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

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

2
5
30 60
40 50
20 100
40 60
10 30

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

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

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

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

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

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

8 2 3
2 1
4 2
6 4
7 2
8 1
10 3
11 2
13 1

При таких исходных данных лягушки преодолеют следующий маршрут: (4, 2), (7, 2), (10, 3), (11, 2). Ответ 3 11.

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

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

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

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

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

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

2

5

30 60

40 1110

59 60

61 120

1230 1440

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

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

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

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

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

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

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

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

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

2

5

30 60

40 60

50 1110

61 1010

1100 1440

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

(Л. Шастин) Во дворце спорта идёт активная продажа билетов на предстоящий баскетбольный матч. Имеется информация об уже распределенных между болельщиками местах. При этом точно известно, что первое и последнее место в каждом из рядов занято. Хорошим называется такое место, что слева и справа от него есть ровно по 5 свободных мест. Найдите ряд с наибольшим номером, в котором есть хотя бы одно хорошее место, а также общее количество хороших мест во всех рядах.

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

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

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

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

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

11

5 1

20 30

5 7

20 18

5 30

20 1

20 4

20 16

5 13

20 10

20 24

Для данного примера подходит ряд 5, в котором слева и справа от 7 места есть ровно по 5 свободных мест, и ряд 20, в котором подходят 10-е и 24-е места. В ответ пойдёт ряд с наибольшим номером, содержащий хорошие места, и общее количество хороших мест. Ответ: 20 3.

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

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

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

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

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

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

1000 7

100 200

0 300

200 430

500 550

550 700

700 800

750 900

При таких условиях вылеты можно максимизировать следующим образом: 100-200; 200-430; 500-550; 550-700; 700-800. Поэтому ответ для приведённого примера 5 700.

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

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

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

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

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

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

Типовой пример организации входных данных
7
40 3
40 7
60 33
50 125
50 129
50 68
50 72

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

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

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

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

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

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

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

5

43

40

32

40

30

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

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

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

(А.Богданов)  В некотором вузе N абитуриентов поступают на некое направление на М мест. Абитуриенты сдали ЕГЭ по русскому языку, профильной математике, физики и/или информатике. В зачет идет 3 экзамена. Если сданы и физика, и информатика, то в зачет идёт максимальный балл из двух предметов. Часть выпускников еще не подала оригиналы документов, что отмечено в исходных данных первым полем (0/1). Необходимо определить гарантированно проходной балл.

Входные данные: в первой строке N – кол-во выпускников, M – кол-во мест на направление и далее N строк для каждого абитуриента, в которых первое число 0/1 (отсутствие/наличие оригиналов документов) и далее 3 или 4 оценки: баллы по русскому, профилю, физике и/или информатике.

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

- проходной балл с учетом наличия оригиналов документов (на момент запроса)
- проходной балл без учета наличия оригиналов документов (верхняя оценка)

Пример:
6 2
0 60 80 90 80
1 61 80 90 80
0 62 80 90 80
1 63 80 90
0 64 80 90
1 65 80 90

С учетом наличия оригиналов документов будут зачислены абитуриенты с баллами 235 и 233. Проходной 233. Без учета документов 235 и 234. Проходной 234.

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

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

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

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

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

5
32
13
85
52
46

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

(3 * 85 + 52 + 46 = 353; 3 * 85 = 255) 

(PRO100 ЕГЭ) В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть 100 000 рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение товаров в чеке?

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

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

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

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

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

5

4

80

30

50

40

Пример входного файла приведён, для покупателя со ста сорока рублями и для акции «каждый второй товар в чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5 (Пример расположения товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139), на второй вопрос число 1 (140 - 139 = 1).

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

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

Тогда покупатель разместил товары по-другому.

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

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

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

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

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

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

4

80

30

50

40

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

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

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

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

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

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

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

В ответе укажите объем свободного места в кэше (в МБ) до удаления первого файла из кэша. И количество файлов в кэше после размещения последнего файла.

Входные данные: В первой строке N и V и далее N чисел по одному в строке.

Выходные данные: Первое число – объем свободного места в кэше (в МБ) до удаления первого файла. Второе - количество файлов в кэше после размещения последнего файла.

Пример:

6 100

30

10

40

50

10

20

До удаления первого файла в кэше будет 100-(30+10+40)=20 МБ. А после кэширования последнего файла в кэше будет 3 файла (50+10+20)

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

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

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

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

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

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

7 3

2

6

7

8

8

10

15

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

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

(А. Игнатюк) Безумный шляпник из страны чудес составлял свой безумный отчет, в котором он зашифровал цены различных товаров. Отчет представлен следующим образом:

7

13 600 700

17 300 400

23 250 800

27 550 200

30 750 350

37 900 200

42 850 170

Число в первой строке обозначает количество позиций в отчете, каждая из которых имеет свой уникальный номер ID, равный первому числу в последующих строках. Второе и третье число обозначают цену на товары, ID которых отличаются от прописанного в текущей строке на -10 и +10, соответственно. Если к ID одного товара можно прийти несколькими способами, в таком случае стоит взять цену, которая встретилась в файле раньше для этого ID. Если подходящего под условия ID не нашлось, значит товара нет в продаже. Необходимо определить:

А) Какое наибольшее количество имеющихся товаров можно закупить, при условии, что цена каждого следующего купленного товара должна отличатся не менее, чем на 50+R, где R - порядковый номер товара в корзине в случае его покупки. Нумерация всех товаров в чеке начинается с 1.

Б) Какая наименьшая цена возможна у купленного товара.

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

Приведем решение для примера выше. По имеющимся данным можно сказать о цене товаров c ID, равными 13, 17, 23, 27 и 37, стоят которые будут 250, 550, 700, 400 и 200, соответственно. Из имеющихся товаров, согласно условию, можно купить товары с ценами 200, 400, 550 и 700. Таким образом, можно купить 4 товара, а минимальная цена у купленного товара равно 200. Ответ: 4 200

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

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

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

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

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

5

43

40

32

40

30

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

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

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

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

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

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

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

5

43

40

32

40

30

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

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

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

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

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

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

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

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

8

50 R

48 G

43 B

40 R

36 B

34 G

22 B

17 R

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

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

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

На карте представлена следующая схема формы записи:

6

3 20 17

6 15 16

7 17 40

5 19 81

9 21 13

11 14 18

Первое число N (1 < N < 300) обозначает количество работающих станций. Далее имеется N строк, содержащих по 3 числа, разделенных пробелом. Первое число в идущих ниже строках обозначает текущий уникальный ID-номер станции, а последующие два числа (всегда различных по величине) указывают на расстояние до станций, ID которых численно отличаются на 1 и 2 в большую сторону соответственно. По имеющимся данным необходимо узнать, до какой станции с максимальным ID-номером можно доехать, если начинать со станции, имеющей наименьший ID, и какое минимальное расстояние можно преодолеть, если при поездке на каждую следующую возможную станцию необходимо всегда выбирать кратчайший маршрут. В качестве ответа указать два числа - сначала минимальное расстояние, а затем номер станции.

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

Приведем решение задачи для примера выше. Из станции 3 можно отправиться на станцию 4 или 5, но поскольку станции с ID = 4 нет, то поехать можно только на станцию c ID = 5, преодолев при этом 17 километров. Из пункта 5 можно отправиться в пункт 6 или 7. Так как до пункта 6 можно добраться, преодолев наименьшее количество километров (19 < 81), выбирается станция с ID = 6. От этой станции можно поехать либо на станцию с ID = 8, либо на станцию с ID = 7. Поскольку станция с ID = 8 отсутствует в списке, необходимо переместиться на станцию с ID = 7, преодолев 15 километров. От станции с ID = 7 передвигаемся на станцию с ID = 9, а затем на станцию с ID = 11. Итого между станциями было пройдено 17 + 19 + 15 + 40 + 13 километров.

Ответ к примеру: 104 11.

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

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

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

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

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

(А.Богданов) Транспортная компания владеет автомобилями с грузоподъемность M. Для транспортировки N грузов автомобили загружают предметами по убыванию веса, пока общая масса предметов не превышает грузоподъемность M. И далее процедуру повторяют для другого грузовика, до тех пор, пока все предметы не будут погружены. Нужно определить количество автомобилей для транспортировки всех предметов и общую загрузку предпоследнего автомобиля.

Входные данные: В первой строке N и M и далее N чисел по одному в строке.

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

 Пример:

 6 100

 30

 10

 40

 50

 10

 20

 В первый автомобиль возьмут 50+40+10, во второй 30+20+10

(А. Игнатюк) В тестовом файле представлен отчет магазина о товарах и акциях за последний месяц. Всего имеется 2 категории товаров: А (товар низкой ценовой категории) и В (товар высокой ценовой категории). Постфикс С, указанный после категории товара, обозначает, что на текущий момент времени на товар действует скидка, процент которой равен остатку при делении на 100 порядкового номера товара. Необходимо узнать минимальную стоимость максимального количества товаров, которые можно купить с учетом денежного лимита, и цену самого дорогого приобретенного со скидкой товара, который можно приобрести при покупке максимального количества товаров.

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

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

В первой строке даны два числа – количество товаров N и денежный лимит S. В каждой из следующих N строк через пробел указано 3 значения: номер товара, цена товара без скидки, категория товара с или без постфикса С.

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

8 820
1 200 А
2 300 ВС
3 150 В
4 270 А
5 350 В
6 240 АС
7 200 ВС
8 300 АС

Товары с порядковыми номерами 2, 6, 7 и 8 подешевеют на 2, 6, 7 и 8 процентов соответственно, их новыми ценами станут суммы 294; 225,6; 186; 276. По условию задачи 1 покупается 4 товара с ценами 150, 186, 200, 225,6, при этом наибольшая возможная цена товара, приобретенного со скидкой, будет 276. Ответом для примера будет: 762 276.

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

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

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

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

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

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

6 4

40 36

32 30

30 14

21 21

17

14

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

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

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

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

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

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

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

Несколько труб, вложенных одна в другую, называют пакетом.

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

Описание входных данных:

В первой строке приведено число N – количество труб. В каждой из следующих N строк приведены пары положительных целых чисел: внешний диаметр трубы D и толщина её стенки S.

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

5

100 5

80 3

74 4

62 5

60 3

При таких исходных данных можно собрать пакет из труб (100, 5), (80, 3), (62, 5). Следовательно, ответ будет

3 62

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

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

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

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

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

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

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

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

5 75
10 1
15 1
25 0
20 0
15 0

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

(М. Ишимов) В городе живут N детей, которые ждут подарки на Новый Год. Снегурочка следит за поведением каждого из них на протяжении всего года. Каждый из ребят отправили письмо Деду Морозу, где написали, что они хотят получить в качестве подарка на Новый Год. Каждое письмо имеет свой номер, причём нечётные номера Снегурочка присвоила письмам от девочек, а чётные номера – письмам от мальчиков. Так как не все дети вели себя хорошо, в список писем от послушных детей Снегурочка записала только письма от M ребят (M < N). Известно, что подарки получат только те, кто попал в список Снегурочки. Определите количество мальчиков, которые вели себя хорошо на протяжении всего года, и количество девочек, которые не получат подарок на Новый Год.

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

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

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

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

8 5

25 48

17 13

16 25

13 93

48 16

39

93

18

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

При таких исходных данных условию задачи удовлетворяет набор мальчиков с номерами писем 48, 16, т.е. количество мальчиков, которые попали в список Снегурочки равно 2, и набор девочек с номерами писем 17, 39, т.е. количество девочек, которые не попали в список Снегурочки равно 2.

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

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

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

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

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

На вход подаётся файл, в котором в первой строке записано число N - количество клиентов, информация о которых записана в отчёте. Затем три столбца, в каждом из которых по N строк. В первом столбце находятся уникальные ID каждого клиента, во втором - количество денег на их счетах, а в третьем - ID клиентов, которым были последовательно сделаны переводы (между собой они разделены знаком ";").

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

3

1 5000 2;3

2 2000 3

3 3000 1

Для данного примера счёт первого клиента изменялся так: 5000 - 2% от 5000 при переводе клиенту №2 = 4900, затем 4900 - 2% от 4900 при переводе клиенту №3 = 4802, после 4802 + 1% от счёта клиента №3 = 4833. Счёт второго клиента изменился в плюс на 2% от 5000 при переводе от клиента №1 = 2100, а после уменьшился на 1% при переводе клиенту №3 = 2079. А счёт третьего клиента сначала пополнился при переводе от первого на 2% от 4900 = 3098, после пополнился при переводе от второго клиента на 1% от 2100 = 3119, а затем уменьшился на 1% при переводе клиенту №1 = 3087. По итогу счёт первого клиента был = 5000, а стал = 4833; второго: 2000 -> 2079; третьего: 3000 -> 3087. В процентном соотношении сильнее всех упал счёт клиента №1, а сильнее всех поднялся счёт клиента №2. Ответ: 1 2.

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

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

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

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

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

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

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

5

63

60

52

60

50

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

При таких исходных данных условию задачи удовлетворяют объекты, расположенные на расстоянии 50, 60 и 63 или 52, 60 и 63 соответственно от нулевой отметки, то есть количество передатчиков равно 3, а расстояние от нулевой отметки до ближайшего к ней передатчика составляет 52.

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

(А. Рогов) В супермаркете покупатели обслуживаются на нескольких кассах. За сутки супермаркет обслужил N покупателей. Известно, что выручка на каждой из касс не превысила M рублей. Определите, какое максимальное количество покупателей могло быть обслужено на одной кассе, а также максимальную сумму чека на данной кассе при условии, что обслужено максимальное количество покупателей.

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

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

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

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

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

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

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

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

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

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

На вход подаётся два числа: N - количество товаров и M - средний чек. Следом N пар чисел.

Первое число в паре - цена (она же вид) товара, второе - его статус (0 - не продан; 1 - продан).

Пример входных данных (для примера N = 5, M = 60):

5 60

43 1

90 1

43 0

43 1

90 0

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

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

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

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

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

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

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

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

1000 7

50 200

0 300

200 450

500 550

550 700

700 800

750 900

При таких условиях расписание можно составить из мероприятий: 50-200; 200-450; 500-550; 550-700; 700-800. Поэтому ответ для приведённого примера 5 700.

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

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

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

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

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

5  

43

40

32

40

30 

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

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

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

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

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

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

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

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

8

1 5

1 6

1 7

1 9

2 1

2 12

1 10

2 24

При таких исходных данных есть два подходящих подъезда в 1-ом доме: № 4 (3 соседних подъезда с жалобами: 5, 6 и 7) и № 8 (4 соседних подъезда с жалобами: 6, 7, 9 и 10). Ответ: 1 4.

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

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

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

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

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

7 6

1 50 2

2 23 1

1 50 6

1 1 1

2 30 5

2 23 6

1 1 6

При таких исходных данных есть два подходящих ряда: 1-й ряд на 1-м этаже и 23-й ряд на 2-м этаже. Ответ: 23 2.

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

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

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

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

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

7 3

1 2

1 3

1 4

1 6

2 1

2 12

2 24

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

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

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

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

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

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

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

4

80

30

50

40

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

160 и 165.

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

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

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

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

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

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

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

4

80

30

50

40

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

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

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

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

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

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

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

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

4

80

30

50

40

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

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

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

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

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

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

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

5

43

40

32

40

30

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

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

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

(А. Богданов) При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу пикселей размером 10000 на 10000 точек.

При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 10000) и номер позиции в строке (целое число от 1 до 10000) и её заряд (+/-).

Положительно заряженная частица включает пиксель, а отрицательно заряженная выключает. Положительная частица не влияет на включенный пиксель, как и отрицательно заряженная на выключенный.

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

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

Специальный спутник принимает сигналы от разных станций на земле. Каждый сигнал имеет координату источника – широту и долготу с точностью до десятых, выраженных целочисленными значениями – удесятеренными координатами. Например, координата 55,7°, 37,6° записывается, как пара чисел 557 376.

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

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

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

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

Два целых числа: целое значение долготы и количество целых градусов широты для нее.

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

7

-123 407

-125 52

-128 52

802 407

809 52

805 407

850 53

Для приведённого примера видим 2 долготы с 3 сигналами: 5,2° и 40,7°. Поэтому считаем количество целых значений широт для 40.7° (-12.3°, 80.2°, 80.5°). Следовательно, принято три сигнала из широт -12° и 80°.

Ответ: 407 2

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

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

- необходимо удалить как можно больше супервирусов;

- нельзя удалять два и более супервируса подряд;

- нельзя удалять супервирус последним.

Входные данные представлены в файле 26.txt следующим образом. Первая строка входного файла содержит количество записей N и общее время T, отведённое на удаление этих вирусов. Каждая из следующих N строк содержит два целых числа: уровень опасности вируса и время, которое требуется для его удаления.

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

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

5 50
7 13
9 20
4 3
8 9
5 5

Средний уровень опасности равен 6.6, значит, суперопасными считаются вирусы с уровнем опасности >= 7. Удаляем сначала супервирус 8-9, далее обычный вирус 4-3, потом снова суперопасный 7-13, затем обычный 5-5. Обычных вирусов не осталось, значит, суперопасные тоже удалять нельзя. Итого удалено 4 вируса. На удаление супервирусов затрачено времени 9 + 13 = 22. Ответ: 4 22.

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

Входные данные представлены в файле 26.txt следующим образом. В первой строке входного файла записано натуральное число N – общее количество занятых мест (1 ≤ N ≤ 600 000). В каждой из следующих N строках находятся по три натуральных числа, не превышающих 25 000. Первые два числа – это номер ряда и место в ряду, занятое участником конференции. Если третье число равно 0, то место занято участником из города Н, а если оно равно 1, то участником из другого города.

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

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

15

1 1 0

1 3 1

1 5 0

1 7 1

1 8 0

2 3 1

2 8 1

2 9 0

2 10 0

3 1 0

3 2 1

3 6 1

3 7 0

3 8 0

3 9 0

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

В 3-м ряду есть 3 свободных места подряд между участниками из других городов (места 3, 4 и 5) и 4 места заняты участниками из города Н. В этом ряду 2 места заняты участниками из других городов (места 2 и 6). Ответ: 3 2.

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

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

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

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

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

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

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

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

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

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

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

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

7

40 3

40 5

60 33

50 125

50 128

50 64

50 66

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

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

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

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

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

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

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

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

7

40 3

40 7

60 33

50 125

50 129

50 68

50 72

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

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

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 10 000) и номер позиции в строке (целое число от 1 до 10 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.

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

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

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

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

7

5 5

2 3

5 7

2 5

5 6

2 5

2 4

При таких исходных данных имеется две цепочки из светлых точек: в позициях 3, 4 и 5 строки 2, и в позициях 5, 6 и 7 строки 5. Обе они включают по 3 светлых точки, минимальный номер строки – 2. Ответ: 3 2.

В терминологии сетей TCP/IP IP-адресом называют 32-битную последовательность, позволяющую однозначно определить подключенное к сети устройство, маской сети называют двоичное число (32 бита), которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске.

Для удобства каждые 8 бит в последовательности разделяются точками.

Например, при IP-адресе 174.23.88.201 и маске 255.255.192.0 адрес сети будет равен 174.23.64.0, адрес узла в этой сети – 6345.

В файле к заданию приведен лог обращений к серверу – IP-адреса, с которых были получены запросы.

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

Формат входных данных:

В первой строке число N – количество обращений к серверу, в каждой из последующих N строках 4 числа, числа, соответствующие числам, разделенным точками.

Формат выходных данных – строка, адрес сети, из которой отправлено максимальное количество запросов, и число, количество узлов в этой сети, которые отправляли запросы. Если сетей, удовлетворяющих условию, нашлось больше одной, выбрать ту, для которой второе число больше. Если и таких сетей несколько, выбрать сеть с наименьшим IP-адресом.

Пример:

5

125 10 13 14

125 10 13 20

125 10 45 14

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

125.10.0.0 2

В дачном кооперативе «Уточка» дядя Дима хочет купить участок размером 200х200 метров. Причем участок он хочет такой, чтобы со всех сторон его окружал лес. У дяди Димы есть результаты аэросъемки района, где он выбирает участок. На нем отмечены все квадраты размером 100х100, на которых расположен лесной массив. Считается, что участки, примыкающие к границе исследованного участка находятся около лесного массива.

Сколько вариантов покупки участка есть у дяди Димы и на какой линии больше всего таких участков? (Каждый участок располагается на двух линиях).

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

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

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

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

Пример: 

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

6 3

Нас интересуют только квадраты 2х2 такие, что все примыкающие участки являются лесным массивом. Предполагается, что участок, состоящий из клеток (6, 1), (6, 2), (7, 1) и (7, 2) примыкает к лесу в неисследованной зоне.

(Калинин А.) Осуществляется посадка кустарников. Причем саженцы высаживают рядами на одинаковом расстоянии.

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

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

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

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

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

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

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

7

40 30

40 34

50 125

50 129

50 64

50 68

50 70

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

50 1

(Калинин А.) В лесополосе осуществляется посадка деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии.

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

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

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

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

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

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

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

7

40 30

40 34

50 125

50 129

50 64

50 68

50 70

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

50 54

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

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

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

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

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

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

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

7

40 3

40 7

60 33

50 125

50 129

50 68

50 72

Ответ для текущего примера: 50 52

В лесополосе осуществляется посадка плодовых деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии. Между соседними саженцами в одном ряду расстояние 10 метров. В каждом ряду сидят разные виды плодовых деревьев.

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

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

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

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

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

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

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

7

1 3

1 5

1 8

2 2

2 5

3 1

3 9

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

4 3

В лесополосе осуществляется посадка деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии.

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

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

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

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

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

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

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

7

40 30

40 34

50 125

50 129

50 64

50 68

50 70

Ответ для примера (при поиске 3 подряд идущих не прижившихся саженцах):

50 65

В магазинах города продают сахар различной стоимости на развес. Количество доступного сахара и его общая стоимость для каждого магазина записаны как натуральные числа: вес не превосходит 1000, стоимость не превосходит 100 000. Зинаиде Михайловне и Алле Петровне для консервации необходимо приобрести К килограмм сахара каждой. С целью экономии каждая сперва покупает сахар с самой низкой ценой за один килограмм. Зинаида Михайловна посетила все магазины первой и купила необходимое ей количество, Алла Петровна покупала позже из оставшегося в магазинах. По заданной информации о сахаре в магазинах и необходимом количестве килограмм определите наименьшую сумму, которую потратят на сахар Зинаида Михайловна и Алла Петровна.

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

Запишите в ответе два числа – наименьшие суммы, которую потратят на сахар Зинаида Михайловна и Алла Петровна.

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

10 100

47 4700

50 6000

60 4800

45 5400

30 3000

15 1800

70 5600

30 3600

91 9100

40 3200

При таких исходных данных самая выгодная стоимость у магазинов с весом 60, 70, 40; затем – с весом 91, 30, 47. Зинаида Михайловна купит 60+40 кг за 8000 рублей; Алла Петровна купит 30+40+30 кг за 8600 рублей.

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

В первой строке содержится количество наблюдателей 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.

В меню бургерной имеется 1000 различных позиций с едой, которым присвоены соответствующие номера (0..999). В бухгалтерском отчёте фиксируют, какие заказы и в какое время были приняты и сделаны. Каждая новая информация о заказе с некоторой позицией говорит о его текущем статусе. Если запись о заказе с некоторой позицией встретилась первый раз, значит, он начал готовиться. Если второй раз, значит, он уже приготовился. Готовить несколько позиций с одним номером в одно время нельзя. Время выдачи заказов стартует в 08:00 утра и длится без перерывов до 00:00 ночи. Известно, что первые заказы на еду начали появляться в 08:00. Вам дана текстовая информация, которая содержалась в отчёте, время не отсортировано.

На вход подаётся число N - общее количество записей (заказов, принятых и готовых). Далее в N строках идут пары чисел: время в минутах (принятие / выдача заказа) и его номер (0..999). Отсчёт времени ведётся с нуля с самого начала смены.

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

1) Какое максимальное количество заказов было завершено в рамках ровно одного часа времени?

2) Какая позиция в среднем значении по продолжительности приготовления самая длительная (среди завершённых заказов)?

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

8

60 5

40 1

90 5

45 5

20 2

55 1

10 2

50 5

За час времени с 10 до 70 (70 - 10 = 60) было приготовлено 3 заказа, это есть часовой локальный максимум.

Позиция 1 в среднем готовилась 15 минут, позиция 2 - 10 минут, а позиция 5 - (30 + 5)/2 = 17.5 минут.

Ответ: 3 5.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 640 на 480 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 640) и номер позиции в строке (целое число от 1 до 480). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.

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

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

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

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

7

1 2

2 3

3 6

2 5

1 4

2 5

2 3

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

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 640 на 480 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 640) и номер позиции в строке (целое число от 1 до 480). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.

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

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

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

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

7

1 2

2 3

3 6

2 4

1 3

2 5

2 4

При таких исходных данных имеется три цепочки светлых точек: в позициях 2 и 3 строки 1, в позициях 4, 5 и 6 строки 2 (это самая длинная цепочка!) и точка в позиции 6 строки 3. Ответ: 3 2.

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает

архив, может быть меньше, чем суммарный объём архивируемых файлов.

Известно, какой объём занимает файл каждого пользователя.

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

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

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

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

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

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

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

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

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

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

6

1 1

1 2

1 3

1 5

1 6

1 7

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

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

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

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

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

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

6

1 1

1 2

1 3

1 4

1 5

1 6

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

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

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

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

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

5

7

1

3

14

1

При таких исходных данных нельзя набрать веса 6, 13, 20. Поэтому ответ для приведённого примера: 3 20

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

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

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

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

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

7

4858

112

4858

4858

31

112

4858

При таких исходных данных имеется 3 различных товара. Наиболее часто встречающийся товар имеет штрихкод 4858. Он встречается 4 раза. Поэтому ответ для приведённого примера: 3 4.

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

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

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

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

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

10

1962 1

1962 2

1962 3

1962 4

1962 6

1962 7

1962 8

1963 4

1964 1

1964 3

При таких входных данных будем считать, что Ивана интересуют только годы с 1962 по 1964.

В 1962 году ему не хватает 1 вида марок; В 1963 году ему не хватает 7 видов марок; В 1964 году ему не хватает 6 видов марок.

Поэтому ответ для приведённого примера 14 1963.

(Д. Ушаков) На производстве станок с ЧПУ обрабатывал некоторый набор деталей. В каждый момент времени станок может обрабатывать только одну деталь. Каждая деталь изготавливалась в определённый промежуток времени с момента начала рабочего дня. Простоем считается временной участок длиной не менее M секунд, в которые не обрабатывается ни одна деталь. Инженер решил узнать, какое количество простоев произошло за день и какова длительность наибольшего простоя. Общая длительность рабочего дня L секунд.

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

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

Запишите в ответе два числа: количество простоев произошло за день и какова длительность наибольшего простоя.

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

1200 100 3

430 300

200 150

900 50

При таких условиях имеется три простоя: 0-200; 730-900; 950-1200. Поэтому ответ для приведённого примера 3 250.

(Д. Ушаков) Брокерская контора решил разделить счета своих клиентов на обычный и премиум сегмент. Известен баланс счёта каждого клиента. Маркетологи взяли эти данные и решили провести границу между двумя сегментами таким образом, что в премиум сегменте окажется не менее 20% клиентов, и при этом разница наименьшего размера счёта клиента из премиум сегмента и наибольшего размера счёта клиента из обычного сегмента максимальна. Если таких максимальных разниц несколько, выбрать ту, при которой премиум клиентов меньше.

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

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

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

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

7

200

550

800

1500

20

750

90

При таких входных данных очевидным премиальным счётом будет 1500, но нельзя включить в премиум сегмент только его, потому что тогда он будет занимать менее 20% от всех счетов. Среди оставшихся разниц в размере (70, 110, 350, 200 и 50) наибольшей является разница 350. Значит премиум сегмент будет содержать 4 счёта (за 550, 750, 800 и 1500). Поэтому ответ для приведённого примера: 4 550

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

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

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

Известно, что видов товаров не бывает более тысячи.

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

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

8 13

150 8

237 3

237 6

150 4

237 5

237 6

150 3

150 3

При таких исходных данных имеется всего два вида товаров ("150" и "237")

Товаров вида "150" можно погрузить три штуки (3, 3 и 4), останется 1 штука (8)

Товаров вида "237" можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6)

Поэтому ответ для приведённого примера: 3 237

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

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

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

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

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

4

8

1

3

1

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

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

На эту сумму библиотеке необходимо закупить максимальное количество книг различных наименований, среди которых должны быть ровно две редкие книги, одна из которых имеет наименьшую стоимость, а другая - наибольшую, также все энциклопедии. Известно, что стоимость редких книг превышает 3000 рублей. Стоимость энциклопедий находится в диапазоне от 2000 до 3000 рублей включительно. Стоимость любой другой книги меньше 2000 рублей.

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

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

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

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

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

11000 8

200

3800

3500

500

3100

800

4100

2500

При таких исходных данных можно приобрести максимум 5 книг: две редкие стоимостью 3100 и 4100, одну энциклопедию за 2500 и две обычных стоимостью 200 и 800. Ответ для приведённого примера 5 800.

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

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

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

10

5 5

5 6

5 7

16 9

16 3

16 6

20 23

20 28

20 29

20 30

В данном примере максимальное количество подряд идущих занятых мест равно 3 (5 ряд места 5, 6, 7 и 20 ряд места 28, 29,30). Ответом будет пара чисел 20 3.

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

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

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

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

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

5 2

220

210

210

200

195

Поступят абитуриенты с баллами 220 и 210, но 210 баллов не гарантирует поступление, поэтому ответ на первый вопрос 220. Не позволяют поступить баллы 200 и 195, их среднее арифметическое 197,5. Ответ на второй вопрос 197.

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

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

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

Пример входного файла (для заданного диапазона от 1000 до 6000)::

6 1000

1300 2200

0 3700

1300 5700

0 0

5000 0

1800 3400

В данном случае наибольшее число запросов (5) выполнялось в интервале времени между 1800 и 2200. Ответ: 5 400.

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

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

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

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

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

7

10 40

50 130

70 130

75 90

120 170

140 170

150 180

При таких исходных данных есть всего два непрерывных проблемных участка: от 10 до 40 и от 50 до 180. Их общая длина 30 + 130. Поэтому ответ для приведённого примера 2 160.

Илье необходимо перенести файлы с одного компьютера на другой при помощи внешнего жесткого диска.

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

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

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

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

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

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

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

100 5

80 A

30 B

20 B

40 A

40 В

При таких исходных данных можно все важные файлы за 2 раза. В первый раз можно перенести файлы 80 А и 20 В, во второй раз 40 А и 40 В. Другой вариант: сначала 80 А и 20 В, затем 40 А и 30 В. В обоих случаях можно перенести все файлы А за 2 раза, помимо них, можно перенести еще 2 файла В. Поэтому ответ 2 2.

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

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

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

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

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

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

7 12

150 8

237 3

150 4

237 5

237 5

150 3

150 3

При таких исходных данных имеется всего два вида компонентов ("150" и "237")

Компонентов вида "150" можно купить три штуки (за 3, 3 и 4)

Компонентов вида "237" можно купить две штуки (за 3 и 5)

Поэтому ответ для приведённого примера

5 18

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

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

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

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

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

6 110

40 E

50 A

50 D

30 C

20 B

10 A

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа A. Минимальная цена такой покупки 110 рублей (покупаем товары 10 A, 20 B, 30 C, 50 A). Останется 0 рублей. Ответ: 2 0.

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

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

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

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

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

6 110

40 Z

50 Q

50 Z

30 Z

20 Q

10 Z

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа Q. Минимальная цена такой покупки 110 рублей (покупаем товары 10 Z, 20 Q, 30 Z, 50 Q). Останется 0 рублей. Ответ: 2 0.

(Л. Шастин) Полина хранит на компьютере картинки и видео, объёмы которых различны. Она хочет сохранить часть из них на флэш-накопитель, объём которого равен M, следующим образом:

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

2) В оставшееся место Полина сохраняет как можно больше картинок, стремясь занять весь оставшийся объём.

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

Входные данные. В первой строке входного файла находятся два числа: N - количество всех изображений и видео, M - объём флеш-накопителя. N, M - натуральные числа, не превышающие 10^6. В следующих N строках находятся значения объёмов картинок и видео соответственно, эти объёмы указаны в Кбайтах. Каждая картинка весит не более 100 Кбайт, видео - не менее 101 Кбайт. Запишите в ответе два числа: сначала объём оставшегося свободного места, затем общее количество картинок и видео, которые могут быть сохранены.

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

8  150

20

101

15

400

5

900

10

9

При таких исходных данных можно сохранить 4 картинки (20+15+5+9 = 49) и 1 видео объёмом 101, имеем: 150 - (49 + 101) = 0;

4 + 1 = 5 - элементов максимум можно сохранить.

Ответ: 0 5.

(А. Богданов) В некотором государстве правительство выделяет K направлений для обучения студентов. На эти места претендуют N абитуриентов. Для каждого направления выделено некоторое количество мест. Для каждого абитуриента известны его баллы и одно выбранное им направление обучения. Зачисление осуществляется в одну волну. На направление зачисляются абитуриенты с максимальными баллами. Требуется определить количество зачисленных абитуриентов по всем направлениям и минимальный балл зачисленного студента (проходной/полупроходной) на направлении с максимальным конкурсом. Под максимальным конкурсом подразумевается отношение количества поданных заявлений к количеству выделенных мест. Гарантируется, что в исходных данных нет направлений с одинаковым конкурсом.

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

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

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

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

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

10

5 5

5 9

5 6

16 9

16 3

16 6

20 23

20 28

20 35

20 40

В данном примере есть следующие свободные места, удовлетворяющие условию: 7 и 8 в ряду 5, 4 и 5 в ряду 16, а также 7 и 8 в ряду 16. Выбираем наибольший номер ряда: 16 и наименьший номер места: 4. В ответе нужно указать: 16 4.

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

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

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

(А. Богданов) Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и N кусков оптоволокна, из которых попросили получить цельные куски по M метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего сварок будет в цельных кусках и сколько метров уйдет в обрезку. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.

Входные данные: в первой строке указаны N, M и в остальных строках размеры выданных кусков.

Например, для данных

10 30

17 15 14 12 11 8 6 5 4 2

Сперва взяли 17 и 14, обрез 1 обратно в кучу [15,12,11,8,6,5,4,2,1]  - 1 сварка

Затем взяли 15,12 и 4, обрез 1 обратно в кучу [11,8,6,5,2,1,1]  - 2 сварки

И затем взяли 11,8,6 и 5, ровно 30, без обреза – 3 сварки.

Итого 6 сварок и в сумме 2 (не штуки, а длины) обреза

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

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

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

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

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

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

100 5

80

30

50

40

20

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

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

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

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

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

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

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

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

100 4

80

30

50

40

При таких исходных данных можно транспортировать за один раз максимум 2 контейнера. Минимальная грузоподъемность одного катера будет 130.

2 130

(А. Богданов) Админ написал скрипт для раскладки N архивов на K дисков, каждый объемом V. Алгоритм скрипта обрабатывает файлы в порядке убывания их размера. Если файл помещается на диск, то следующий по размеру файл стараются поместить на следующий диск. Если не помещается, то на следующий и так по кругу. Если файл не поместился ни на один диск, то он откладывается в локальную папку. Укажите в ответе два числа: объем всех отложенных файлов и их количество.

Входные данные: в первой строке указаны V, K, N и в остальных строках размеры каждого из N архивов.

Например, для данных

20 3 10

17 15 13 12 11 7 6 4 3 2

ответ будет: 31 и 4 

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

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

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

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

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

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

100 4 

80 

30 

50 

40 

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

2 50

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

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

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

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

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

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

100 7

10

44

66

90

65

47

34

При таких исходных данных в архив можно записать файлы максимум 3 пользователей. При этом максимально возможная сумма будет из файлов размером 10, 34, 47. А файлы размером 65, 66, 90 не смогут попасть в архив ни при каких условиях.

Ответ к приведённому примеру входных данных

91 3

В текстовом файле записан набор натуральных чисел, не превышающих 10⁹.

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

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

Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.

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

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

6

3

8

14

11

22

17

В данном случае есть две подходящие пары: 3 и 8 (сумма 11), 3 и 14 (сумма 17).

В ответе надо записать числа 2 и 17.

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

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

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

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

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

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

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

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

В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары с чётной суммой, такие что:

- хотя бы половина чисел набора меньше среднего арифметического пары

- хотя бы четверть чисел набора больше среднего арифметического пары

Определите количество таких пар и наименьшее из средних арифметических таких пар.

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

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

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

8

3

8

14

11

2

16

5

9

В данном случае есть четыре подходящие пары: 2 и 16 (среднее арифметическое 9), 8 и 14 (среднее арифметическое 11), 9 и 11 (среднее арифметическое 10), 8 и 16 (среднее арифметическое 12). В ответе надо записать числа 4 и 9.

Системный администратор раз в неделю создаёт архив пользовательских файлов. Файлы разделяются на две максимально равные по размеру и количеству группы. Архив создается в два этапа. На первом этапе файлы с одинаковым размером распределяются на два жестких диска – первая половина файлов на первый диск, вторая – на второй. На первом этапе всегда распределяется четное количество файлов. Файлы, не попавшие в одну из двух групп распределяются на втором этапе.

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

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

Пример организации исходных данных во входном файле (каждое число с новой строки):

10

10 20 30 10 20 70 80 30 30 100

При таких исходных данных на втором этапе будет сохранено 4 файла : 30, 70, 80 и 100. На втором этапе файлы разделятся на две группы: 100+30, 70+80. Разница составит 20.

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

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

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

10 3 2

1800

3600

3700

800

2600

2500

1800

1500

1900

1200

При таких исходных данных ответ должен содержать два числа – 1800 и 2420.

Пояснение: скидка 20% будет на товары стоимостью 3700, 3600, 2600 и 10% на товары стоимостью 2500 и 1900. Тогда самый дорогой товар без скидки стоит 1800, а сумма скидок 740+720+520+250+190 = 2420.

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

За какое минимальное количество рейсов можно перевезти все грузы?

Входные данные представлены в файле следующим образом. В первой строке входного файла записаны два целых числа: N – общее количество грузов и S – грузоподъёмность грузового судна в тоннах. Каждая из следующих N строк содержит одно целое число < S – массу груза в тоннах.

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

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

6 500

140

150

160

200

220

240

При таких входных данных ответ будет 3 и 150.

Первым рейсом будет отправлено 2 груза – 240 и 220, вторым – 200, 160 и 140, третьим – 150.

Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 310 до 320 кг грузят в первую очередь. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.

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

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

6 720

100

315

120

160

140

300

В данном случае сначала нужно взять груз массой 315 кг. Остается 405 кг. После этого можно вывезти ещё максимум 3 груза. Это можно сделать тремя способами: 100 + 120 + 140, 100 + 140 + 160, 100 + 120 + 160. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов два: 100 + 120 + 160, 100 + 140 + 160. Из этих способов выбираем тот, при котором больше масса второго по величине груза, то есть 100 + 140 + 160. Всего получается 4 груза общей массой 715 кг. Ответ: 4 715.

Системный администратор раз в неделю создаёт архив пользовательских файлов. Файлы размещаются на двух дисках.

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

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

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

Запишите в ответе два числа: сначала количество файлов, сохраненное на первом диске, затем – на втором.

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

5

80

30

10

50

45

При таких исходных данных на первом диске будут сохранены файлы размером 80 и 50, на втором – 10, 30, 45. Поэтому ответ для приведённого примера:

2 3

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

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

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

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

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

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

100 5

80

30

10

5

7

При таких исходных данных можно сохранить файлы трех пользователей. Объёмы этих трех файлов 80, 5 и 10. Последний выбранный файл имеет размер 10 , поэтому ответ для приведённого примера:

Системный администратор раз в неделю создаёт архив пользовательских файлов. Причем файлы размером больше 500 МБ записывает на диск D, а меньшего размера на диск E.

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

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

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

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

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

3000 1000 6

300

350

400

1000

1500

2000

При таких исходных данных можно сохранить четыре файла – 350 и 400 (300 и 400) на диске E, 1000 и 2000 на диске D. Поэтому ответ должен содержать два числа – 4 и 2400.

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

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

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

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

10 4

47 470

50 600

60 480

45 540

30 300

15 180

70 560

30 360

91 910

40 320

При таких исходных данных самая выгодная стоимость у пакетов весом 60, 70, 40; затем – у пакетов весом 91, 30, 47. Поэтому наибольший возможный вес к отправке равен 70+60+40+91 = 261, а стоимость самого большого отправленного пакета равна 910.

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

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

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

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

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

10 2

34

50

43

44

23

9

39

5

38

36

При таких исходных данных ответ должен содержать 2 числа – 43 и 35. Пояснение: будут отброшены значения 5, 9, 44, 50. Тогда наибольшее оставшееся значение равно 43, а среднее значение из оставшихся равно (23+34+36+38+39+43):6 = 35,5.

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

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

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

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

10 3 2

28500

12000

17500

25000

18000

20000

22500

7500

19000

5500

При таких исходных данных ответ должен содержать 2 числа – 25000 и 8333. Пояснение: стоимость смартфонов из бюджетного сегмента: 5500, 7500, 12000; стоимость смартфонов из премиум сегмента – 25000 и 28500. Минимальная цена премиум смартфона 25000, а средняя цена бюджетного 8333,33.

Магазин предоставляет оптовому покупателю скидку по следующим правилам:

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

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

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

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

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

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

7

225

160

380

95

192

310

60

В данном случае товары с ценой 60, 95, 160 и 192 не участвуют в определении скидки, остальные товары магазину выгодно расположить в таком порядке цен: 380, 225, 310. Скидка предоставляется на товар ценой 225. Его цена со скидкой составит 157,5 руб., после округления – 158 руб. Общая цена покупки составит: 60 + 95 + 160 + 192 + 158 + 380 + 310 = 1355 руб. Самый дорогой товар, на который будет получена скидка, стоит 225 руб. В ответе нужно записать числа 1355 и 225.

В магазине проводят акция – каждый второй товар со скидкой 50%. При этом в акции участвуют только те товары, разница в цене которых находятся в диапазонах 1-500, 501-1000, 1001-1501 и т.д. Например, при наличии в чеке только позиций с ценами 300 и 1000 предложение акции не работает.

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

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

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

Пример входного файла (все значения с новой строки):

10

100 50 15 160 500 1002 2003 2010 2350 2400

При таких исходных данных ответ должен содержать 2 числа – 2039 и 1005.

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

Первая акция – 30% скидки на 70% самых дешевых товаров, 40% процентов скидки на оставшиеся товары.

Вторая акция – 40% скидки на 50% самых дешевых товаров, 35% процентов скидки на оставшиеся товары.

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

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

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

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

Пример входного файла (все значения с новой строки):

20

4 13 4 23 22 20 8 6 5 12 48 22 50 12 63 23 4 8 9 11

При таких исходных данных ответ должен содержать 2 числа – 1 и 40.

В проекте «СкупойПлатитДважды» 1 января решено тратить на развитие 60% накоплений всех участников. При этом 20% самых богатых участников вносят 80% от своих накоплений, остальные участники вносят равный процент таким образом, чтобы общая сумма взносов всех участников составила 60%, обозначенные выше.

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

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

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

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

10

10

12

25

25

40

35

18

19

10

12

При таких исходных данных ответ должен содержать 2 числа – 60 и 4.

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

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

Каждый файл в архиве может быть либо сжат, либо сохранен в исходном состоянии. Сжатый файл занимает в памяти 80% от исходного. Для архива выделяется объем, равный 90% от общего объема файлов пользователей до сжатия.

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

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

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

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

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

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

7

13

17

5

55

61

9

10

При таких исходных данных ответ должен содержать 2 числа – 5 и 17.

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

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

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

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

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

Гарантируется, что N > K.

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

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

5 3

60

30

50

40

10

При таких исходных данных Петр может собрать суммарно максимум 150 фантиков за 3 дня (40+50+60 = 150)

Наименьшие количество собранных главным героем фантиков за один день оказалось – 40

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

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

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

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

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

8

10

12

8

6

20

12

16

10

При таких исходных данных после ремонта объем ям будет выглядеть следующим образом 10, 10, 8, 8, 12, 16, 12, 10. В ответе необходимо указать два числа – 2 и 14.

Системный администратор раз в неделю создаёт архив пользовательских файлов. Выделяемый объем памяти рассчитывается, как общий объем файлов за вычетом количественно 10% файлов – 5% составляют самые мелкие файлы и 5% составляют самые крупные файлы. Известно, какой объём занимает файл каждого пользователя.

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

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

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

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

Пример входного файла (для вычета 20% файлов):

10

50

33

44

17

92

58

42

10

52

88

При таких исходных данных можно сохранить 8 файлов – 50, 33, 44, 17, 58, 42, 52, 88. Поэтому ответ должен содержать два числа – 384 и 88.

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

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

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

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

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

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

100 4

70

10

25

3

При таких исходных данных можно сохранить три файла – 70, 25, 3. Поэтому ответ должен содержать два числа – 3 и 3

На вход программе поступает набор чисел в диапазоне [10; 10000]. Необходимо узнать сколько чисел в массиве находятся в диапазоне между средним значением и медианой, включая совпадающие с этими показателями значения. 

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

В качестве ответа дать одно число – количество найденных чисел. 

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

7 

10 

47 

60 

84 

65 

47 

37 

При таких исходных результатом является число 2. Среднее значение равно 50, медиана – 47

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

Робот складывает монеты в ящики. Задача робота заполнить как можно большее количество ящиков монетами в количестве 100 штук. Роботу по конвейеру поступают корзины с монетами. В каждой корзине может быть от 1 до 99 монет.

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

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

Входные данные представлены в файле следующим образом. В первой строке записано число 1 < N < 10000 – количество корзин, в каждой из последующих N строк целое число 0 < K < 100 – количество монет в каждой корзине.

В качестве ответа дать одно число – количество ящиков, заполненных 100 монетами.

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

7

10

44

66

90

65

47

34

При таких исходных данных можно заполнить только 2 ящика по 100 монет 10 + 90 и 66 + 34. 

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

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

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

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