(Л. Шастин) На склад магазина привезли 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$ соответственно), а остальные покупатели не смогли ничего приобрести. Ответ: $473$.

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

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

Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 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.

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