recursum
Каталог
Найдено: 87
В кинотеатре находятся M рядов, в каждом из которых имеется K мест. Ряды и
места в каждом ряду пронумерованы натуральными числами начиная с 1. Известно,
какие места уже забронированы зрителями.
На специальный показ планируют пригласить семьи, в каждой из которых по L
человек. Администратор хочет разместить в одном ряду как можно больше семей.
Каждая семья должна занимать L свободных мест с последовательными номерами.
Места, занятые разными семьями, не должны пересекаться, при этом семьи могут
сидеть вплотную друг к другу.
Определите наибольший номер ряда, в котором можно разместить максимальное
количество семей, и это количество семей.
Входные данные
В первой строке входного файла находятся четыре натуральных числа: N —
количество забронированных мест (N ≤ 100 000), M — количество рядов
(M ≤ 100 000), K — количество мест в каждом ряду (K ≤ 100 000) и L —
количество человек в каждой семье (2 ≤ L ≤ K). В следующих N строках находятся
пары натуральных чисел: номер ряда и номер забронированного места
соответственно.
Гарантируется, что в каждом ряду есть хотя бы одно забронированное место и
хотя бы в одном ряду можно разместить одну семью.
Выходные данные
Запишите два целых числа: сначала наибольший номер ряда, в котором можно
разместить максимальное количество семей, затем это количество семей.
Типовой пример организации данных во входном файле
6 3 12 3
1 4
1 8
2 6
3 3
3 7
3 11
При таких исходных данных в рядах 1 и 2 можно разместить по три семьи, а в
ряду 3 — две семьи. Из двух подходящих рядов выбирается ряд с наибольшим
номером. Ответом является пара чисел 2 и 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания
используйте данные из прилагаемого файла.
Файлы к заданию:
В концертном зале находятся M рядов, в каждом из которых имеется K мест.
Ряды пронумерованы от сцены начиная с 1, места в каждом ряду также
пронумерованы начиная с 1. Известно, какие места уже заняты зрителями.
Для проведения телевизионной съёмки требуется установить площадку, которая
занимает L мест с последовательными номерами в одном ряду. Поскольку площадка
может мешать зрителям, все места с теми же номерами в рядах, расположенных
дальше от сцены, должны быть свободны. Места, на которых устанавливается
площадка, также должны быть свободны.
Определите наименьший номер ряда, в котором можно установить площадку, и
количество различных вариантов её размещения в найденном ряду. Два варианта
считаются различными, если у них различаются номера первых мест. Варианты могут
пересекаться.
Входные данные
В первой строке входного файла находятся четыре натуральных числа: N —
количество занятых мест (N ≤ 100 000), M — количество рядов (M ≤ 100 000),
K — количество мест в каждом ряду (K ≤ 100 000) и L — количество мест,
занимаемых площадкой (2 ≤ L ≤ K). В следующих N строках находятся пары
натуральных чисел: номер ряда и номер занятого места соответственно.
Гарантируется, что существует хотя бы один вариант размещения площадки.
Выходные данные
Запишите два целых числа: сначала наименьший номер ряда, затем количество
вариантов размещения площадки в этом ряду.
Типовой пример организации данных во входном файле
8 7 8 3
2 1
4 2
4 3
1 4
3 5
2 6
1 7
6 8
При таких исходных данных площадку можно установить в ряду 4 на местах с
номерами 4, 5, 6 или на местах с номерами 5, 6, 7. В рядах с меньшими номерами
подходящих вариантов нет. Ответом является пара чисел 4 и 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания
используйте данные из прилагаемого файла.
Файлы к заданию:
Автоматизированный склад представляет собой прямоугольный стеллаж из $M$
горизонтальных уровней и $K$ вертикальных секций. Уровни пронумерованы сверху
вниз, начиная с 1, секции — слева направо, также начиная с 1. Некоторые ячейки
стеллажа заняты грузами.
С верхнего края стеллажа вертикально опускают горизонтальную платформу. Она
должна занять не менее двух соседних ячеек одного уровня. Длина платформы может
быть любой. При опускании все ячейки в выбранных секциях от первого уровня до
уровня размещения платформы включительно должны быть свободны.
Определите наибольший номер уровня, на котором можно разместить платформу, и
максимальную возможную длину платформы на этом уровне.
Входные данные
В первой строке входного файла находятся три натуральных числа: $N$ —
количество занятых ячеек, $M$ — количество уровней и $K$ — количество
вертикальных секций. В следующих $N$ строках находятся пары натуральных чисел:
номер уровня и номер секции занятой ячейки соответственно.
Гарантируется, что существует хотя бы одно подходящее место для платформы
длиной не менее двух ячеек.
В ответе запишите два целых числа: сначала наибольший номер уровня, затем
максимальную длину платформы на этом уровне.
Файлы к заданию:
В кинотеатре $M$ рядов, в каждом из которых находится $K$ мест. Ряды
пронумерованы от экрана, начиная с 1, места в каждом ряду также пронумерованы
начиная с 1. Известно, какие места уже заняты.
Группа из четырёх зрителей хочет занять четыре места с последовательными
номерами в одном ряду. Подходящим считается только такое размещение, при
котором выбранные места свободны и все места с этими же четырьмя номерами во
всех рядах, расположенных ближе к экрану, также свободны.
Найдите наибольший номер ряда, в котором возможно такое размещение, и
количество различных четвёрок мест, подходящих для группы в найденном ряду.
Две четвёрки считаются различными, если у них различаются номера первых мест;
четвёрки могут пересекаться.
Входные данные
В первой строке входного файла находятся три натуральных числа: $N$ —
количество занятых мест, $M$ — количество рядов и $K$ — количество мест в
каждом ряду. В следующих $N$ строках находятся пары натуральных чисел: номер
ряда и номер занятого места соответственно.
Гарантируется, что существует хотя бы одна подходящая четвёрка мест.
В ответе запишите два целых числа: сначала наибольший номер ряда, затем
количество подходящих четвёрок в этом ряду.
Файлы к заданию:
Система наблюдения ежеминутно фиксирует вход и выход сотрудников из офиса (в минутах, прошедших от начала суток). Считается, что в моменты фиксации входа и выхода сотрудник находится в офисе. Нулевая минута соответствует моменту начала рабочего дня в офисе, который работает 24 ч в сутки без перерыва.
Менеджер компании анализирует данные системы наблюдения за прошедшие сутки и выявляет непересекающиеся отрезки времени наибольшей длины, в течение которых число сотрудников, находящихся в офисе, не изменялось.
Определите минуту, когда в предпоследний раз за сутки число сотрудников поменялось, и укажите наибольшую длину отрезка времени, когда количество сотрудников оставалось неизменным.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 100 000) – количество сотрудников компании. Следующие N строк содержат пары чисел, обозначающих соответственно время входа и время выхода сотрудника (все числа натуральные, не превышающие 1440).
Выходные данные
Два натуральных числа: сначала минуту, когда в предпоследний раз за сутки число сотрудников поменялось, а затем наибольшую длительность промежутка времени, при котором количество сотрудников оставалось неизменным.
Типовой пример организации данных во входном файле
5
10 100
101 200
150 400
401 500
500 900
При таких исходных данных в течение суток было 7 промежутков времени, когда число сотрудников не менялось: (0, 10), (10, 150), (150, 201), (201, 500), (500, 501), (501, 901), (901, 1440). Наибольшей длиной из этих отрезков является число 539. В 501 минуту в предпоследний раз изменилось число сотрудников. Заметим, что в 101 минуту один сотрудник ушёл, а другой пришёл, поэтому число сотрудников не изменилось: сотрудник, вышедший в 100-ю минуту, находился в офисе в течение этой минуты.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
На складе хранятся $N$ защитных контейнеров и $M$ электронных пломб. У каждого контейнера есть числовой код. Контейнеры можно вкладывать один в другой, образуя цепочку: каждый следующий контейнер должен иметь код больше предыдущего хотя бы на $7$.
Для каждого контейнера определяется тип. Если код контейнера кратен $3$, контейнер имеет тип A, иначе тип B. В цепочке соседние контейнеры должны иметь разные типы. Кроме того, контейнер можно использовать только в том случае, если для него найдётся подходящая электронная пломба. Пломба подходит к контейнеру, если её маркировка равна остатку от деления кода контейнера на $100$. Каждую пломбу можно использовать не более одного раза.
Нужно определить наибольшее количество контейнеров, которое можно включить в одну цепочку вложения. Если существует несколько цепочек максимальной длины, нужно выбрать такую, в которой код самого маленького контейнера как можно больше.
Входные данные
В первой строке входного файла находятся два числа $N$ и $M$: количество контейнеров и количество электронных пломб. В следующих $N$ строках записаны коды контейнеров. Затем в следующих $M$ строках записаны маркировки пломб.
Запишите в ответе два целых числа: сначала наибольшее количество контейнеров в цепочке, затем максимально возможный код самого маленького контейнера среди цепочек такой длины.
Файлы к заданию:
В магазине канцтоваров проводится акция. Товары, цена которых меньше $500$ рублей, продаются без скидки. Для остальных товаров действует правило: в каждом чеке каждый четвёртый товар из участвующих в акции продаётся за $40%$ своей цены.
Порядок товаров в чеке определяет кассовая система магазина. Она располагает товары так, чтобы общая сумма скидки в этом чеке была наименьшей. Общая стоимость каждого чека после применения скидок округляется вверх до целого числа рублей.
Покупатель может разбить все товары на несколько чеков произвольным образом. Он хочет сделать это так, чтобы заплатить за всю покупку как можно меньше.
Входные данные
В первой строке входного файла находится число $N$ - количество товаров, которые хочет купить покупатель. В следующих $N$ строках находятся натуральные числа, обозначающие цены товаров. Цены указаны в произвольном порядке.
Запишите в ответе два целых числа: сначала минимальную сумму, которую заплатит покупатель при оптимальном разбиении на чеки, затем сумму, которую он заплатит, если купит все товары одним чеком.
Файлы к заданию:
На автоматизированном складе смена робота должна непрерывно продолжаться с момента $S$ до момента $F$. Для питания робота можно использовать сменные аккумуляторные блоки. Каждый блок имеет известный промежуток работы: с момента $a$ до момента $b$, то есть может питать робота на интервале $[a; b)$.
В каждый момент времени должен быть подключён ровно один блок. Нужно выбрать минимальное количество блоков так, чтобы робот мог работать без перерыва на всём интервале $[S; F)$. Если таких способов несколько, выберите способ, при котором первый подключённый блок будет заменён как можно позже.
Входные данные
В первой строке входного файла находятся три натуральных числа $N$, $S$ и $F$: количество аккумуляторных блоков, момент начала смены и момент окончания смены. В следующих $N$ строках находятся пары натуральных чисел $a$ и $b$, задающие промежуток работы одного блока.
Гарантируется, что среди данных блоков можно обеспечить непрерывную работу робота на всём интервале $[S; F)$.
В ответе запишите два целых числа: сначала минимальное количество блоков, затем длительность работы первого выбранного блока с момента $S$ до его замены.
Файлы к заданию:
В кинотеатре известно, какие места уже забронированы зрителями. В каждом ряду места пронумерованы натуральными числами от $1$ до $1000$. Группе из $6$ человек нужно выделить подряд идущие свободные места в одном ряду.
Администратор рассматривает только такие варианты размещения, при которых в этом же ряду слева от группы есть хотя бы одно уже забронированное место, не обязательно соседнее с группой. Кроме того, справа от группы должно остаться хотя бы одно свободное место.
Нужно найти ряд с наибольшим номером, в котором можно разместить группу по этим правилам. Если в этом ряду есть несколько подходящих вариантов, выберите тот, в котором первое место группы имеет наибольший номер.
Входные данные
В первой строке входного файла находится число $N$ - количество уже забронированных мест. В следующих $N$ строках находятся пары натуральных чисел: номер ряда и номер места в этом ряду.
Гарантируется, что существует хотя бы один ряд, удовлетворяющий условию.
В ответе запишите два целых числа: номер найденного ряда и номер первого места в группе из $6$ подряд идущих свободных мест.
Файлы к заданию:
Задание выполняется с использованием прилагаемого файла.
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 11:59:59.
Входные данные
Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1,000,000$) — количество строк в журнале и $K$ ($K < 1,000,000$) — вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1,000,000$) — идентификатор клиентского устройства и $S$ ($S < K$) — объём данных запроса в Кбайт.
Выходные данные
В ответе запишите два числа: сначала идентификатор устройства, с которого был передан наибольший суммарный объём данных, а затем сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, выполненных не позднее 11:59:59.
Типовой пример организации данных во входном файле
8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000
При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 05:05:05 (в объёме 130 000 Кбайт), в 07:07:07 (в объёме 90 000 Кбайт), в 21:21:21 (в объёме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт). Всего на сервер передано 596 000 Кбайт данных: 158 000, 122 000, 182 000 и 134 000 Кбайт от клиентов с идентификаторами 101, 202, 303 и 404 соответственно.
Ответ для приведённого примера: 303 220 000.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос - в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда для сохранения данных в этом разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает специальный раздел и продолжает
выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите сумму идентификаторов двух клиентских устройств, с которых на сервер был передан наименьший общий объём данных, а также сумму объёмов (в Кбайт) двух последних по времени резервных копий специального раздела, выполненных не позднее 11:59:59.
Входные данные
Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: N(N< 1 000 000) - количество строк
в журнале и К (К < 1 000 000) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: (С < 1 000 000) - идентификатор клиентского устройства и S (S < K) - объём данных запроса в Кбайт.
Выходные данные
В ответе запишите два числа: сначала сумму идентификаторов двух устройств, с которых на сервер был передан наименьший общий объём данных, а затем сумму объёмов (в Кбайт) двух последних по времени резервных копий специального раздела, выполненных не позднее 11:59:59.
Типовой пример организации данных во входном файле
8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000
При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 05:05:05 (в объёме 130 000 Кбайт), в 07:07:07 (в объёме 90 000 Кбайт), в 21:21:21 (в объёме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт).
Всего на сервер должно быть передано 596 000 Кбайт данных: 158 000, 122 000, 182 000 и 134 000 Кбайт от клиентов с идентификаторами 101, 202, 303 и 404 соответственно. Ответ для приведённого примера: 606 220 000
Типовой пример имеет иллюстративный характер.
Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
Сервер выполняет запросы на передачу данных. Сведения о каждом запросе — время регистрации, идентификатор клиента и объём данных — сохраняются в журнале, а данные помещаются в специальный раздел памяти ограниченного объёма. Если для очередного запроса свободной памяти недостаточно, сервер создаёт резервную копию всех накопленных данных, освобождает раздел и продолжает выполнение запросов.
Напишите программу для обработки журнала и определите:
- наибольший суммарный объём данных, переданный с одного клиентского устройства и не превышающий 150 000 Кбайт;
- сумму объёмов двух последних по времени резервных копий, созданных не позднее 11:59:59.
Входные данные
В первой строке файла записаны натуральные числа $N$ $(N<1,000,000)$ — количество запросов и $K$ $(K<1,000,000)$ — вместимость раздела памяти в Кбайт. Каждая из следующих $N$ строк содержит время в формате ЧЧ:ММ:СС и два натуральных числа: $C$ $(C<1,000,000)$ — идентификатор клиента и $S$ $(S<K)$ — объём запроса в Кбайт.
Выходные данные
Запишите искомый суммарный объём данных с одного клиентского устройства и сумму объёмов двух последних резервных копий.
Пример входных данных
8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000
Для этих данных резервные копии создаются в 05:05:05 (130 000 Кбайт), 07:07:07 (90 000 Кбайт), 21:21:21 (122 000 Кбайт) и 23:23:23 (120 000 Кбайт). Ответ для примера: 134000 220000.
Пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
Сервер выполняет запросы на передачу данных. Сведения о каждом выполненном запросе — время регистрации, идентификатор клиента и объём переданных данных — сохраняются в журнале работы, а сами данные помещаются в специальный раздел памяти ограниченного объёма. Если для очередного запроса свободной памяти недостаточно, сервер создаёт резервную копию всех накопленных данных, освобождает раздел и продолжает выполнение запросов.
Напишите программу для обработки журнала и определите:
- идентификатор клиентского устройства, с которого не позднее 11:59:59 был передан наибольший суммарный объём данных;
- сумму объёмов двух наибольших резервных копий специального раздела, в Кбайт.
Входные данные
В первой строке файла записаны натуральные числа $N$ $(N<1,000,000)$ — количество запросов и $K$ $(K<1,000,000)$ — вместимость раздела памяти в Кбайт. Каждая из следующих $N$ строк содержит время регистрации в формате ЧЧ:ММ:СС и два натуральных числа: $C$ $(C<1,000,000)$ — идентификатор клиента и $S$ $(S<K)$ — объём данных запроса в Кбайт.
Выходные данные
Запишите два целых положительных числа: идентификатор искомого клиентского устройства и сумму объёмов двух наибольших резервных копий.
Пример входных данных
8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000
Для этих данных резервные копии создаются в 05:05:05 (130 000 Кбайт), 07:07:07 (90 000 Кбайт), 21:21:21 (122 000 Кбайт) и 23:23:23 (120 000 Кбайт). Клиенты 101, 202, 303 и 404 передали соответственно 158 000, 122 000, 182 000 и 134 000 Кбайт. Ответ для примера: 101 252000.
Пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
Вдоль дороги длиной 10 км расположены дома. В течение дня жители отправляют в управляющую компанию заявки на уборку снега. В каждой заявке указано, с какой точки (в метрах от начала дороги) нужно начать уборку и какова длина участка (в метрах), который требуется очистить.
Если участки дороги в двух или более заявках имеют общую часть дороги, то можно выполнить не более одной из таких заявок. Если
конец одного участка совпадает с началом другого, то нужно убрать оба участка.
Определите, наибольшее количество заявок, которые может выполнить управляющая компания, и в этом случае минимальную длину неубранного участка, расположенного в конце дороги (в метрах).
Входные данные
Первая строка входного файла содержит целое число N (N ⩽ 2000) - количество заявок на уборку снега. Следующие N строк содержат
пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не
превосходящее 10 000. Гарантируется, что конец участка не выходит за пределы дороги.
В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем - минимально возможную при таком количестве заявок длину неубранного участка, расположенного конце дороги (в метрах).
Типовой пример организации данных во входном файле
5
1 1000
1001 1000
2001 2500
4501 500
4501 1500
При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5. Ответ: 4 3999.
Файлы к заданию:
В кондитерской есть N круглых форм для коржей. Специализация кондитерской – многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 8 единиц меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.
Входные данные
В первой строке входного файла находится число N — количество форм для коржей в кондитерской (натуральное число, не превышающее 10000). В следующих N строках находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.
*Выходные данные *
Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем - максимально возможный диаметр самого маленького коржа в таком торте.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящих для изготовления многоярусного торта, составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
На грузовом космическом корабле необходимо перевезти на МКС контейнеры, имеющие одинаковые габариты и разные массы. Общая масса всех этих контейнеров превышает грузоподъёмность космического корабля. Количество грузовых мест на космическом корабле не меньше числа контейнеров, назначенных к перевозке.
Определите количество и наибольшую возможную суммарную массу контейнеров, которые останутся на космодроме, после того, как на космический корабль загрузят как можно большее возможное количество контейнеров.
Входные данные
В первой строке входного файла находятся два числа: S - грузоподъёмность космического корабля (натуральное число, не превышающее 100 000) и N - количество контейнеров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки на МКС (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Выходные данные
Два целых неотрицательных числа: минимальное количество контейнеров, которые нельзя перевезти на МКС за один рейс, и максимальная суммарная масса оставшихся на космодроме грузов.
Типовой пример организации данных во входном файле
100 4
80
30
50
40
*При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров - **30 и 40, 30 и 50 или 40 и 50. Контейнеры с массами 50 и 80 могут быть не перевезены. Ответом для приведённого примера является *пара чисел 2 и 130.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
Менеджеры интернет-магазина составляют рейтинговый список новых моделей смартфонов по данным о продолжительности автономной работы устройства в режиме ожидания и в активном режиме использования. У каждой модели известны оба показателя. Для объективности бренды и марки устройств скрыты, в списке все смартфоны пронумерованы начиная с единицы.
Алгоритм формирования рейтинга выглядит следующим образом:
- все 2N чисел, обозначающих продолжительности работы в режиме ожидания и в режиме активного использования для N устройств, располагаются по возрастанию;
- если наименьший показатель соответствует продолжительности работы в режиме ожидания, устройство занимает первое свободное место от начала рейтинга;
- если наименьший показатель относится к продолжительности работы в активном режиме использования смартфона, устройство занимает первое свободное место от конца рейтинга;
- показатели устройств, ранее включённых в рейтинговый список, игнорируются.
Определите порядковый номер смартфона, чей рейтинг будет определён последним, и количество устройств, занявших позиции ниже него.
Запишите в ответе два натуральных числа: сначала номер последнего устройства, для которого будет определено его место в рейтинге, затем количество устройств, которые займут в рейтинге более низкие места.
Входные данные
первой строке входного файла находится натуральное число N (N ≤ 1000) - количество смартфонов. Следующие N строк содержат пары чисел, обозначающих соответственно продолжительность работы устройства в режиме ожидания в режиме активного использования (все числа натуральные, различные).
Типовой пример организации данных во входном файле
5
800 120
150 200
250 300
60 100
180 220
Пример организации данных приведён для пяти смартфонов.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером $M \times K$, где $M$ — количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$), $K$ — количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$). Нумерация горизонтальных рядов поля идёт сверху вниз с $1$, а вертикальных — слева направо также с $1$. Некоторые клетки поля уже заняты кораблями ($n$-палубный корабль занимает, соответственно, $n$ подряд идущих клеток).
Пете необходимо разместить 1-палубный корабль, расположив его на свободной клетке игрового поля так, чтобы до ближайшего по направлению вверх препятствия (корабля, части многопалубного корабля или края игрового поля) было как можно больше свободных клеток. Допускается ставить корабли вплотную друг к другу.
Если горизонтальных рядов для удовлетворяющего условию размещения корабля несколько, то необходимо указать горизонтальный ряд с наименьшим номером. Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.
Входные данные.
В первой строке входного файла находятся три числа: $N$ — количество клеток игрового поля, в которых расположены однопалубные корабли или части многопалубных кораблей ($N$ — целое положительное число, не превышающее $100,000$), $M$ — количество горизонтальных рядов игрового поля и $K$ — количество вертикальных рядов игрового поля. В следующих $N$ строках соответственно находятся пары натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового поля, в которых расположены корабли или их части (первое число не превышает значения $M$, а второе — $K$).
В ответе запишите два целых числа: номер горизонтального ряда и количество свободных клеток до ближайшего по направлению вверх препятствия.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Дети играют в следующую игру. На бесконечном разлинованном на клетки листе введена декартова система координат, при этом клетки таковы, что их вершины находятся во всех точках плоскости, для которых обе координаты целочисленные. Есть некоторое количество бумажных квадратов, стороны которых имеют целочисленные длины. Дети помещают на плоскость эти квадраты (возможно, не все) так, что нижний левый угол каждого квадрата находится на биссектрисе координатного угла, идущей из третьей четверти в первую, и стороны квадратов параллельны осям координат. При этом положение каждого квадрата заранее определено.
Входной файл содержит сведения о размерах квадратов и их возможных положениях на плоскости. Для каждого квадрата указана целочисленная абсцисса положения его нижнего левого угла и длина стороны. Если при размещении на плоскости один квадрат накрывает другой, то дети должны оставить только один из них. Если стороны квадратов касаются, то можно оставить на плоскости оба квадрата.
Определите максимальное количество квадратов, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних углов двух квадратов, наиболее удалённых от начала координат.
Входные данные.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество квадратов. Следующие $N$ строк содержат пары чисел, обозначающих абсциссу положения левого нижнего угла квадрата на плоскости и длину его стороны. Каждое из чисел целое, не превосходящее $10,000$.
Запишите в ответе два числа: максимальное количество квадратов и максимальную величину модуля разности абсцисс положений левых нижних углов двух квадратов, наиболее удалённых от начала координат.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
На прямолинейном участке пути для обеспечения связи необходимо разместить радиопередатчики. Установка каждого такого передатчика возможна на любом из $N$ объектов, включённых в перечень разрешённых. Известно расстояние от нулевой отметки на этом участке до каждого объекта из данного перечня.
По техническим нормативам для работы без помех два соседних передатчика должны находиться на расстоянии не менее $6$ единиц друг от друга. На данном участке пути необходимо разместить максимальное количество передатчиков, не нарушая технические нормативы.
В первой строке входного файла находится число $N$ ($N \le 10,000$) — количество объектов, на которых можно устанавливать передатчики. В следующих $N$ строках находятся натуральные расстояния от нулевой отметки до объектов, каждое в отдельной строке.
Запишите в ответе два целых числа: сначала максимальное количество передатчиков, затем максимально возможное расстояние от нулевой отметки до ближайшего к ней передатчика при таком размещении.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
В тематическом парке для строительства арт-объектов используются однородные прямые круговые цилиндры с одинаковыми высотами; таких цилиндров заготовлено $N$ штук.
Руководством парка рабочим поставлена задача создать максимальной высоты пирамиду из поставленных друг на друга цилиндров, такую, чтобы каждый следующий цилиндр имел радиус основания не менее чем на $7$ единиц меньше, чем предыдущий, чтобы у посетителей парка была возможность на образовавшиеся уступы помещать различные мелкие предметы.
Определите количество цилиндров, которое нужно использовать для создания такой пирамиды, и максимально возможный радиус основания цилиндра, который будет находиться на вершине такой пирамиды.
В первой строке входного файла находится число $N$ - количество цилиндров ($N \le 10000$). В следующих $N$ строках находятся значения длин радиусов имеющихся цилиндров, все числа натуральные, не превышающие $10000$, каждое - в отдельной строке.
Запишите в ответе два целых числа: сначала количество цилиндров, которое необходимо использовать для строительства пирамиды максимальной высоты, затем максимально возможную длину радиуса цилиндра, который можно поместить на вершину такой пирамиды.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета на изображении (номера рядов пикселей и номера чёрных пикселей в ряду).
Для редактирования изображения Пете нужно изменить цвет с белого на чёрный трём соседним подряд идущим белым пикселям, таким что слева и справа от них в том же ряду пиксели чёрные.
Найдите ряд с наименьшим номером, в котором есть три соседних подряд идущих белых пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию.
Входные данные
В первой строке входного файла находится число $N$ — количество рядов пикселей (натуральное число, не превышающее 10000). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих 100000: номер ряда и номер чёрного пикселя в ряду.
Запишите в ответе два целых числа: номер ряда и наибольший номер пикселя в ряду из найденных в этом ряду подходящих троек белых пикселей.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Организаторам спортивных соревнований необходимо доставить как можно большее число команд в некоторый город. Для доставки используются самолёты определённой пассажировместимости. Входной файл содержит сведения о количестве человек в команде и о пассажировместимости самолётов, которые имеются в наличии.
Из соображений безопасности в одном самолёте может лететь только одна команда, а количество занятых спортсменами мест должно быть не больше, чем количество свободных мест (т. е. пассажировместимость используемого для транспортировки команды самолёта должна быть не менее чем вдвое больше количества человек в команде).
Найдите способ доставить на соревнования максимально возможное число команд. Если способов несколько, то нужно выбрать такой, чтобы можно было доставить команду с максимальным числом участников.
Входные данные.
В первой строке входного файла находятся два натуральных числа $N$ ($N \le 1000$) и $M$ ($M \le 1000$) — количество команд и количество самолётов соответственно. Следующие $N$ строк содержат числа, обозначающие количество человек в команде, затем идут $M$ строк, где указана пассажировместимость самолётов. Числа $M$ и $N$ могут быть не равны.
Запишите в ответе два натуральных числа: сначала максимальное количество команд, которые могут прибыть на соревнования, затем максимальную численность команды в этом случае.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Входной файл содержит сведения о мероприятиях, в которых приглашён участвовать директор фирмы. Для каждого мероприятия указаны время начала и длительность его проведения (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то руководитель может принять участие только в одном из них. Если время окончания одного мероприятия совпадает со временем начала другого, то руководитель может принять участие в обоих мероприятиях (очно или дистанционно).
Определите, в каком максимальном количестве мероприятий может принять участие руководитель и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество заявок на проведение мероприятий. Следующие $N$ строк содержат пары чисел, обозначающих время начала и длительность мероприятия. Каждое из чисел натуральное, не превосходящее $1440$.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета на изображении (номера рядов пикселей и номера чёрных пикселей в ряду).
Для редактирования изображения Пете нужно изменить цвет с белого на чёрный всем имеющимся трём соседним подряд идущим белым пикселям, таким что слева и справа от них в том же ряду пиксели чёрные.
Найдите ряд с наибольшим номером, в котором есть три соседних подряд идущих белых пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию.
Входные данные
В первой строке входного файла находится число $N$ — количество рядов пикселей (натуральное число, не превышающее 10000). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих 100000: номер ряда и номер чёрного пикселя в ряду.
Запишите в ответе два целых числа: номер ряда и наименьший номер пикселя в ряду из найденных в этом ряду подходящих троек белых пикселей.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Петя участвует в расширенной версии игры «Морской бой». В данной версии игры,
в отличие от классической, допускается увеличение количества и длины кораблей,
а игровое поле может быть прямоугольным, размером $M \times K$, где $M$ —
количество горизонтальных рядов клеток на игровом поле (целое положительное
число, не превышающее $100,000$), $K$ — количество вертикальных рядов клеток
на игровом поле (целое положительное число, не превышающее $100,000$).
Нумерация горизонтальных рядов поля идёт сверху вниз с $1$, а вертикальных —
слева направо также с $1$. Некоторые клетки поля уже заняты кораблями
($n$-палубный корабль занимает, соответственно, $n$ подряд идущих клеток).
Пете необходимо разместить 2-палубный корабль, расположив его на свободных
клетках некоторого одного ряда так, чтобы корабль находился как можно дальше
от верхнего края игрового поля и все клетки игрового поля, находящиеся
непосредственно над ним, не были заняты другими кораблями. Допускается ставить
корабли вплотную друг к другу.
Если в найденном для размещения корабля ряду мест, удовлетворяющих условию,
несколько, то найдите место с наименьшими номерами вертикальных рядов.
Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.
Входные данные.
В первой строке входного файла находятся три числа: $N$ — количество клеток
игрового поля, в которых расположены однопалубные корабли или части
многопалубных кораблей ($N$ — целое положительное число, не превышающее
$100,000$), $M$ — количество горизонтальных рядов игрового поля и $K$ —
количество вертикальных рядов игрового поля. В следующих $N$ строках
соответственно находятся пары натуральных чисел: номер горизонтального ряда
и номер вертикального ряда игрового поля, в которых расположены корабли или
их части (первое число не превышает значения $M$, а второе — $K$).
Запишите в ответе два целых числа: номер горизонтального ряда и наименьший
из двух номеров вертикальных рядов, где необходимо разместить корабль.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером $M \times K$, где $M$ — количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$), $K$ — количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$). Нумерация горизонтальных рядов поля идёт сверху вниз с $1$, а вертикальных — слева направо также с $1$. Некоторые клетки поля уже заняты кораблями ($n$-палубный корабль занимает, соответственно, $n$ подряд идущих клеток).
Пете необходимо разместить 1-палубный корабль, расположив его на свободной клетке игрового поля так, чтобы до ближайшего по направлению вверх препятствия (корабля, части многопалубного корабля или края игрового поля) было как можно больше свободных клеток. Допускается ставить корабли вплотную друг к другу.
Если горизонтальных рядов для удовлетворяющего условию размещения корабля несколько, то необходимо указать горизонтальный ряд с наименьшим номером. Если в найденном для размещения корабля горизонтальном ряду мест, удовлетворяющих условию, также несколько, то найдите место с наименьшим номером вертикального ряда. Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.
Входные данные.
В первой строке входного файла находятся три числа: $N$ — количество клеток игрового поля, в которых расположены однопалубные корабли или части многопалубных кораблей ($N$ — целое положительное число, не превышающее $100,000$), $M$ — количество горизонтальных рядов игрового поля и $K$ — количество вертикальных рядов игрового поля. В следующих $N$ строках соответственно находятся пары натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового поля, в которых расположены корабли или их части (первое число не превышает значения $M$, а второе — $K$).
Запишите в ответе два целых числа: номер горизонтального ряда и номер вертикального ряда, где необходимо разместить корабль.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
В магазине для упаковки подарков есть $N$ кубических коробок и $M$ декоративных замочков к ним ($M < N$). Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек.
Одну коробку можно поместить в другую, если длина её стороны хотя бы на $6$ единиц меньше длины стороны другой коробки. Замочек подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки.
В первой строке входного файла находятся числа $N$ и $M$. В следующих строках находятся значения длин сторон коробок и маркировки замочков; каждая пара значений записана в отдельной строке, а в последних $N-M$ строках второе число опускается.
Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки. В ответе запишите два целых числа.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером $M \times K$, где $M$ — количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$), $K$ — количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее $100,000$). Нумерация горизонтальных рядов поля идёт сверху вниз с $1$, а вертикальных — слева направо также с $1$. Некоторые клетки поля уже заняты кораблями ($n$-палубный корабль занимает, соответственно, $n$ подряд идущих клеток).
Пете необходимо разместить 3-палубный корабль, расположив его на свободных клетках некоторого одного ряда так, чтобы корабль находился как можно дальше от верхнего края игрового поля и все клетки игрового поля, находящиеся непосредственно над ним, не были заняты другими кораблями. Допускается ставить корабли вплотную друг к другу.
Если в найденном для размещения корабля ряду мест, удовлетворяющих условию, несколько, то найдите место с наибольшими номерами вертикальных рядов. Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.
Входные данные.
В первой строке входного файла находятся три числа: $N$ — количество клеток игрового поля, в которых расположены однопалубные корабли или части многопалубных кораблей ($N$ — целое положительное число, не превышающее $100,000$), $M$ — количество горизонтальных рядов игрового поля и $K$ — количество вертикальных рядов игрового поля. В следующих $N$ строках соответственно находятся пары натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового поля, в которых расположены корабли или их части (первое число не превышает значения $M$, а второе — $K$).
Запишите в ответе два целых числа: номер горизонтального ряда и наибольший из трёх номеров вертикальных рядов, где необходимо разместить корабль.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Дети играют в следующую игру. На бесконечном разлинованном на клетки листе введена декартова система координат, при этом клетки таковы, что их вершины находятся во всех точках плоскости, для которых обе координаты целочисленные. Есть некоторое количество бумажных прямоугольников, стороны которых имеют целочисленные длины. Дети помещают на плоскость эти прямоугольники (возможно, не все) так, что нижний левый угол каждого прямоугольника находится на биссектрисе координатного угла, идущей из третьей четверти в первую, и стороны прямоугольников параллельны осям координат. При этом положение каждого прямоугольника заранее определено.
Входной файл содержит сведения о размерах прямоугольников и их возможных положениях на плоскости. Для каждого прямоугольника указана целочисленная абсцисса положения его нижнего левого угла, длина горизонтальной стороны, длина вертикальной стороны. Если при размещении на плоскости один прямоугольник накрывает другой, то дети должны оставить только один из них. Если стороны прямоугольников касаются, то можно оставить на плоскости оба прямоугольника.
Определите максимальное количество прямоугольников, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних углов двух прямоугольников, наиболее удалённых от начала координат.
Входные данные.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество прямоугольников. Следующие $N$ строк содержат тройки чисел, обозначающих абсциссу положения левого нижнего угла прямоугольника на плоскости, длину его горизонтальной стороны, длину его вертикальной стороны. Каждое из чисел целое, не превосходящее $10,000$.
Запишите в ответе два числа: максимальное количество прямоугольников и максимальную величину модуля разности абсцисс положений левых нижних углов двух прямоугольников, наиболее удалённых от начала координат.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета: номера рядов пикселей и номера чёрных пикселей в ряду.
Для редактирования изображения Пете нужно изменить цвет с белого на чёрный у всех имеющихся двух соседних белых пикселей, таких что слева и справа от них в том же ряду пиксели чёрные.
Найдите ряд с наибольшим номером, в котором есть два соседних пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию.
В первой строке входного файла находится число $N$ — количество чёрных пикселей ($N \le 10,000$). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100,000$: номер ряда и номер чёрного пикселя в ряду.
Запишите в ответе два целых числа: номер ряда и наименьший номер пикселя в найденной паре белых пикселей.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета на изображении (номера рядов пикселей и номера чёрных пикселей в ряду).
Для редактирования изображения Пете нужно изменить цвет с белого на чёрный всем имеющимся двум соседним белым пикселям, таким что слева и справа от них в том же ряду пиксели чёрные.
Найдите ряд с наименьшим номером, в котором есть два соседних пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию.
Входные данные
В первой строке входного файла находится число $N$ — количество рядов пикселей (натуральное число, не превышающее 10000). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих 100000: номер ряда и номер чёрного пикселя в ряду.
Запишите в ответе два целых числа: номер ряда и наибольший номер пикселя в ряду из найденных в этом ряду подходящих пар белых пикселей.
Примечание. В дополнительных материалах приведён типовой пример организации данных во входном файле, имеющий иллюстративный характер.
Файлы к заданию:
Задание выполняется с использованием прилагаемых файлов.
Организаторам спортивных соревнований необходимо доставить как можно большее число команд в некоторый город. Для доставки используются самолёты определённой пассажировместимости. Входной файл содержит сведения о количестве человек в команде и о пассажировместимости самолётов, которые имеются в наличии.
Из соображений безопасности в одном самолёте может лететь только одна команда, а количество занятых спортсменами мест должно быть не больше, чем количество свободных мест (т. е. пассажировместимость используемого для транспортировки команды самолёта должна быть не менее чем вдвое больше количества человек в команде). Найдите способ доставить на соревнования максимально возможное число команд. Если способов несколько, то нужно выбрать такой, чтобы можно было доставить команду с максимальным числом участников.
Входные данные.
В первой строке входного файла находятся два натуральных числа $N$ ($N \le 1000$) и $M$ ($M \le 1000$) — количество команд и количество самолётов соответственно. Следующие $N$ строк содержат числа, обозначающие количество человек в команде, затем идут $M$ строк, где указана пассажировместимость самолётов. Числа $M$ и $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 (1 < N < 1 000 000) - количество участков CHT и К (1 < K < 100 000) - количество моделей снегоуборщиков соответственно.
Следующие N строк содержат по одному натуральному числу, не превышающему 1000, минимальные мощности снегоуборщиков, которые можно закупить для каждого из N участков. Далее в каждой из К строк содержится пара натуральных чисел - мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 1000, стоимость - 100 000. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.
Выходные данные
В ответе укажите два искомых числа: суммарную стоимость всех купленных снегоуборщиков и максимальную мощность среди них.
Типовой пример организации данных во входном файле
3 4
1
2
3
10 7
1 5
3 7
2 3
При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью 2 и стоимостью 3, для третьего участка будет закуплен снегоуборщик мощностью 10. Стоимость закупки составит 3 + 3 + 7 = 13. Ответ: 13; 10.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Дана изначальная коробка. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $D + K$ единиц меньше длины стороны другой коробки, где $K$ — порядковый номер внешней коробки в матрёшке (изначальная коробка имеет номер $0$). Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, а также минимально возможную длину стороны самой большой коробки, где будет находиться подарок.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000), S - изначальная коробка (натуральное число, не превышающее 10 000) и D (натуральное число, не превышающее 1 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем минимально возможную длину стороны самой большой коробки в таком наборе.
Типовой пример организации данных во входном файле
5 26 6
50
41
33
40
55
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 26, 33, 41, 50 или 26, 33, 41, 55, т.е. количество коробок равно 4, а минимальная длина стороны самой большой коробки равна 50
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
На соревнованиях по спортивнориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер - натуральное число, не превышающее 1 000 000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем.
Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее
число спортсменов с идущими подряд номерами. Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки.
Входные данные
В первой строке входного файла находится число N (натуральное число, не превышающее 1 000 000) - количество посещений спортсменами контрольных точек в течение всего сезона соревнований. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: номер спортсмена и номер посещённой им контрольной точки.
Выходные данные
Два целых неотрицательных числа: максимальное число спортсменов с идущими подряд номерами, посетивших одну и ту же
точку, и номер этой точки.
Типовой пример организации входных данных
9
41 3
43 125
50 33
42 125
42 126
*42 *127
41 125
50 126
42 126
Для приведённого примера точку с номером 125 посетили три спортсмена с номерами 41, 42 и 43. Ответом является пара чисел: 3; 125.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов
Файлы к заданию:
Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток).
Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.
Входные данные
В первой строке входного файла находится натуральное число К, не превышающее 1000, - количество окон в МФЦ. Во второй строке
натуральное число N (N ≤ 10 000), обозначающее количество граждан. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в заявке время начала и время окончания приёма (в минутах от начала суток).
Запишите в ответе два числа: количество граждан, которые смогут воспользоваться услугами МФЦ, и номер окна, в котором специалист примет последнего гражданина.
Типовой пример организации данных во входном файле
2
5
30 60
40 100
59 60
61 100
101 144
При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, - 1, так как будут свободны окна 1 и 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
Входной файл содержит сведения о массе грузов, поступивших в транспортную компанию, и о параметрах контейнеров, которые у неё имеются. В один контейнер может быть упакован только один груз. Определите максимальное количество грузов, которое может быть упаковано, и максимально возможную разность двух самых тяжёлых грузов в этом случае.
Входные данные:
В первой строке входного файла находятся два натуральных числа N (N ≤ 1000) и М (М ≤ 1000) - количество грузов и количество контейнеров соответственно. Следующие N строк содержат числа, обозначающие массы грузов, затем идут М строк, где указана максимально допустимая масса груза для размещения в конкретном контейнере. Числа М и N могут быть не равны.
Выходные данные:
Запишите в ответе два натуральных числа: сначала максимальное количество грузов, которое может быть упаковано, затем максимально возможную разность двух самых тяжёлых грузов в этом случае.
Типовой пример организации данных во входном файле:
5 6
170
200
130
170
100
150
150
180
130
130
200
При таких исходных данных максимальное количество грузов, которое может быть упаковано в контейнеры, равно 4, если взять грузы массой 110, 130, 170 и 170 соответственно. Максимальная разность двух самых тяжёлых грузов в наборе составит 30, если взять грузы массой 110, 130, 170 и 200 соответственно.
Файлы к заданию:
На производстве штучных изделий 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 кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон
подходящих коробок составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки –
подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны меньше длины стороны другой коробки не менее чем на 9 единиц. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000).
В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
*Пример входного файла приведён для пяти коробок и случая, когда *минимальная допустимая разница между длинами сторон коробок,
*подходящих для упаковки «матрёшкой», не менее 3 единиц. *При таких исходных данных условию задачи удовлетворяют наборы
*коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, **т.е. количество коробок равно 3, а длина стороны самой маленькой *коробки равна 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
В банке дистанционной проверяющей системы имеется более 100 000 заданий. Все задачи пронумерованы начиная с единицы. Эти задания в течение учебного периода решают участники различных курсов. Каждому студенту при регистрации присваивается уникальный идентификатор - натуральное число, не превышающее 1 000 000. Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.
Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество
задач из банка через одну (одну решил, следующую нет и т.д.).
Определите идентификационный номер студента, который решил наибольшее количество задач через одну, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите студента с наименьшим идентификационным номером.
Входные данные
В первой строке входного файла находится число N - количество зачтённых решений (натуральное число, не превышающее 60 000) за некоторый период времени. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: идентификатор студента и номер правильно решённой задачи.
Выходные данные
Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество успешно решённых задач через одну.
Типовой пример организации входных данных
9
40 3
60 33
60 33
50 124
50 126
50 128
40 4
50 72
50 126
Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач через одну (3 задачи).
Ответом является пара чисел: 50; 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме
того, можно получить дополнительное 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) - натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется
по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке
выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов - с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.
Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, противном случае полупроходной балл отсутствует.
В ответе запишите два целых числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл.
Если полупроходной балл отсутствует, то второе число в ответе должно быть равно нулю.
Входные данные
В первой строке входного файла находятся два натуральных числа, не превышающих 10 000, через пробел: число N - количество кандидатов и число К - количество мест в отряде. В следующих N строках находятся по 5 чисел через пробел: ID кандидата (натуральное число, не превышающее 100 000) и четыре целых неотрицательных числа - сначала результаты испытаний, затем результат собеседования.
Выходные данные
Два числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл.
Типовой пример организации данных во входном файле
6 4
4 80 80 80 0
7 50 80 100 10
11 80 80 70 10
10 100 100 100 2
6 90 90 90 9
2 70 80 80 8
*При таких исходных данных рейтинговый список из ID составлен следующим образом: 10 6 7 11 4 2. Два кандидата с баллами 302 и 279 зачислены, проходной балл 279. На оставшиеся два места претендуют три человека, набравшие по 240 баллов, хотя из троих будут зачислены только двое. Таким образом, 240 - полупроходной балл.
Ответ: 6 3
*
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В банке дистанционной проверяющей системы имеется более 100000 заданий. Все задачи пронумерованы, начиная с единицы. Эти задания в течение учебного периода решают участники различных курсов. Каждому студенту при регистрации присваивается уникальный идентификатор – натуральное число, не превышающее 1000000. Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.
Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество задач из банке с идущими подряд номерами, не пропустив ни одной.
Определите идентификационный номер студента, который решил наибольшее количество задач с идущими подряд номерами, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите наименьший идентификационный номер.
Входные данные
В первой строке входного файла находится число N – количество зачтённых решений (натуральное число, не превышающее 60000) за некоторый период времени. Каждая из следующих N строк содержит два натуральных числа, не превышающих 100000: идентификатор студента и номер правильно решённой задачи.
Выходные данные
Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество решённых задач с подряд идущими номерами.
Типовой пример организации входных данных
9
40 3
60 33
60 33
50 125
50 126
50 127
40 4
50 72
50 126
Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач с идущими подряд номерами (3 задачи). Ответом является пара чисел: 50; 3
Типовой пример носит иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID.
Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов
с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.
Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 25 % мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 25 % студентов.
Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».
В ответе запишите два целых положительных числа: сначала ID студента, который занимает последнее место среди студентов с повышенной стипендией, затем ID первого в рейтинговом списке студента, который имеет более двух «двоек».
Входные данные
В первой строке входного файла находится число N, обозначающее количество студентов (целое положительное число, не превышающее 10 000). Каждая из следующих N строк содержит 5 чисел через пробел: ID студента (целое положительное число, не превышающее 100 000) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов N кратно 4 и хотя бы один студент имеет более двух «двоек». Во входном файле все ID различны.
Выходные данные
Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.
Типовой пример организации данных во входном файле
8
4 4 4 4 4
7 5 5 5 2
10 3 4 4 5
1 4 4 4 3
6 3 5 5 3
2 2 2 2 2
13 2 2 2 3
3 3 3 3 3
При таких исходных данных рейтинговый список ID имеет вид:
4 6 10 1 3 7 13 2. Ответ: 6 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В супермаркете проводится акция «каждый девятый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил все товары на ленте на группы, по девять товаров в каждой. За каждую группу он собирался заплатить отдельным чеком. В каждой группе из девяти товаров самый дорогой он поместил на девятое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной.
Тогда покупатель разместил товары по-другому.
Входные данные
В первой строке входного файла находится число N — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих N строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое — в отдельной строке).
Цены товаров указаны в произвольном порядке.
Запишите в ответе два целых числа: сначала минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 9-й товар в любой покупке, состоящей из 9 предметов. Затем запишите цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом.
Типовой пример организации данных во входном файле
4
80
50
30
40
При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 160.
Файлы к заданию:
В магазине продаётся N товаров нескольких артикулов. Товары одного артикула имеют одинаковую цену. Учёт товаров ведётся поштучно, для каждой единицы товара известен её текущий статус (продана или нет). Товары разделены на две категории: дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает среднюю цену (среднее арифметическое) всех товаров в базе данных магазина без учёта их текущего статуса, остальные товары считаются дешёвыми.
Лидером продаж называется товар с таким артикулом, наибольшее количество единиц которого продано. Лидер продаж выбирается среди дорогих товаров, а если продано одинаковое количество дорогих товаров с разными артикулами, лидером выбирается товар с наибольшей ценой. Если и таких товаров несколько, лидер продаж — тот из них, которого осталось меньше всего.
Найдите суммарную выручку магазина от реализации товара — лидера продаж, а также оставшееся количество товара этого артикула.
Входные данные
В первой строке входного файла находится число N — количество товаров в базе данных магазина (натуральное число, не превышающее 10 000). В каждой из следующих N строк находится три числа, разделённых пробелом: артикул товара (натуральное число, не превышающее 100 000), его цена (натуральное число, не превышающее 10 000) и статус (0, если товар уже продан, и 1, если ещё не продан).
Выходные данные
Два числа: сумма выручки от реализации товара — лидера продаж, а также количество товара этого артикула, оставшееся в наличии.
Типовой пример организации данных во входном файле
8
10 100 1
3 10 0
10 100 0
2 10 1
10 100 0
3 10 1
11 100 0
1 200 0
При таких исходных данных дорогими являются товары стоимостью 100 и 200 рублей. Больше всего было продано товара вида 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ 200 1.
Файлы к заданию:
Отбор кандидатов в матросы происходит по сумме баллов трех экзаменов. На заранее известное количество мест отбираются кандидаты, набравшие большую сумму баллов по результатам трех экзаменов. Все кандидаты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом. Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование, а при равенстве баллов за собеседование – приоритет имеют кандидаты с наименьшими ID.
Для данного множества кандидатов следует определить ID последнего кандидата с набранным проходным баллом, а также каково количество кандидатов, набравших полупроходной балл.
Входные данные
В первой строке входного файла находится два числа N – количество кандидатов (натуральное число, не превышающее 1000) и S – количество имеющихся мест. Каждая из следующих N строк содержит пять чисел: ID кандидата (натуральное число, не превышающее 10 000), соответственно три оценки по экзаменам (все числа целые неотрицательные, не превышающие 100) и балл за собеседование (целое неотрицательное число, не превышающее 10).
Запишите в ответе два целых числа: сначала ID последнего кандидата с набранным проходным баллом, а затем количество кандидатов,
набравшие полупроходной балл.
Типовой пример организации данных во входном файле
6 3
1 90 90 90 10
3 60 70 80 8
5 63 60 90 6
8 50 80 100 4
4 40 95 80 7
11 80 63 72 6
При таких входных данных проходной балл равен 230, полупроходной 215, на оставшееся одно место будет назначен кандидат, набравший в сумме 215 баллов и получивший по собеседованию 7 баллов. Ответ для приведённого примера: 8 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места
в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.
Входные данные
В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10000), М — количество рядов (целое положительное число, не превышающее 100 000) и К — количество, мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения М, а второе — К).
Выходные данные
Два целых положительных числа: наибольший номер ряда и наибольший номер места в найденной паре кресел.
Типовой пример организации данных во входном файле
7 7 8
1 1
6 6
5 5
6 7
4 4
2 2
3 3
При таких исходных данных ответом является пара чисел 5 и 8. Условию задачи удовлетворяют места 7 и 8 в ряду 5: перед
креслами 7 и 8 нет занятых мест и это последняя из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию: