Задачи
Найдено: 84
На складе хранятся $N$ защитных контейнеров. У каждого контейнера есть числовой код. Контейнеры можно вкладывать один в другой, образуя цепочку: каждый следующий контейнер должен иметь код больше предыдущего хотя бы на $7$.
Для каждого контейнера определяется тип. Если код контейнера кратен $3$, контейнер имеет тип $A$, иначе тип $B$. В цепочке соседние контейнеры должны иметь разные типы.
Нужно определить наибольшее количество контейнеров, которое можно включить в одну цепочку вложения. Если существует несколько цепочек максимальной длины, нужно выбрать такую, в которой код самого маленького контейнера как можно больше.
Входные данные
В первой строке входного файла находится натуральное число $N$ — количество контейнеров. В следующих $N$ строках записаны натуральные числа — коды контейнеров.
Выходные данные
Запишите в ответе два целых числа: сначала наибольшее количество контейнеров в цепочке, затем максимально возможный код самого маленького контейнера среди цепочек такой длины.
Типовой пример организации данных во входном файле
7
100
101
108
115
123
130
138
При таких исходных данных можно составить цепочку из шести контейнеров с кодами 101, 108, 115, 123, 130 и 138. Их типы чередуются, разность соседних кодов не меньше 7. Цепочка из семи контейнеров невозможна. Ответом является пара чисел 6 и 101.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В магазине канцтоваров проводится акция. Товары, цена которых меньше $500$ рублей, продаются без скидки. Для остальных товаров действует правило: в каждом чеке каждый четвёртый товар из участвующих в акции продаётся за $40$ % своей цены.
Порядок товаров в чеке определяет кассовая система магазина. Она располагает товары так, чтобы общая сумма скидки в этом чеке была наименьшей. При расчёте каждого чека округление не выполняется. После сложения стоимости всех чеков общая стоимость покупки округляется вверх до целого числа рублей.
Покупатель может разбить все товары на несколько чеков произвольным образом. Он хочет сделать это так, чтобы заплатить за всю покупку как можно меньше.
Входные данные
В первой строке входного файла находится число $N$ - количество товаров, которые хочет купить покупатель. В следующих $N$ строках находятся натуральные числа, обозначающие цены товаров. Цены указаны в произвольном порядке.
Выходные данные
Запишите в ответе два целых числа: сначала минимальную сумму, которую заплатит покупатель при оптимальном разбиении на чеки, затем сумму, которую он заплатит, если купит все товары одним чеком.
Типовой пример организации данных во входном файле
8
600
700
800
900
1000
1100
1200
1300
При таких исходных данных выгодно выделить в один чек товары стоимостью 1000, 1100, 1200 и 1300 рублей, а в другой — оставшиеся четыре товара. Скидка применяется к товарам стоимостью 1000 и 600 рублей. При покупке одним чеком скидка применяется к товарам стоимостью 600 и 700 рублей. Ответом является пара чисел 6640 и 6820.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В кинотеатре находятся $M$ рядов, в каждом из которых имеется $K$ мест. Ряды и места в каждом ряду пронумерованы натуральными числами начиная с 1. Известно, какие места уже забронированы зрителями.
На специальный показ планируют пригласить семьи, в каждой из которых по $L$ человек. Администратор хочет разместить в одном ряду как можно больше семей. Каждая семья должна занимать $L$ свободных мест с последовательными номерами. Места, занятые разными семьями, не должны пересекаться, при этом семьи могут сидеть вплотную друг к другу.
Определите наибольший номер ряда, в котором можно разместить максимальное количество семей, и это количество семей.
Входные данные
В первой строке входного файла находятся четыре натуральных числа: $N$ — количество забронированных мест ($N \le 100\thinspace 000$), $M$ — количество рядов ($M \le 100\thinspace 000$), $K$ — количество мест в каждом ряду ($K \le 100\thinspace 000$) и $L$ — количество человек в каждой семье ($2 \le L \le 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 \le 100\thinspace 000$), $M$ — количество рядов ($M \le 100\thinspace 000$), $K$ — количество мест в каждом ряду ($K \le 100\thinspace 000$) и $L$ — количество мест, занимаемых площадкой ($2 \le L \le 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$ строках находятся пары натуральных чисел: номер уровня и номер секции занятой ячейки соответственно.
Гарантируется, что существует хотя бы одно подходящее место для платформы длиной не менее двух ячеек.
Выходные данные
В ответе запишите два целых числа: сначала наибольший номер уровня, затем максимальную длину платформы на этом уровне.
Типовой пример организации данных во входном файле
4 4 8
1 1
2 6
3 3
4 8
При таких исходных данных платформу можно опустить до уровня 4 в секциях 4 и 5. Более длинной свободной полосы с полностью свободными ячейками над ней на этом уровне нет. Ответом является пара чисел 4 и 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В кинотеатре $M$ рядов, в каждом из которых находится $K$ мест. Ряды пронумерованы от экрана, начиная с 1, места в каждом ряду также пронумерованы начиная с 1. Известно, какие места уже заняты.
Группа из четырёх зрителей хочет занять четыре места с последовательными номерами в одном ряду. Подходящим считается только такое размещение, при котором выбранные места свободны и все места с этими же четырьмя номерами во всех рядах, расположенных ближе к экрану, также свободны.
Найдите наибольший номер ряда, в котором возможно такое размещение, и количество различных четвёрок мест, подходящих для группы в найденном ряду. Две четвёрки считаются различными, если у них различаются номера первых мест; четвёрки могут пересекаться.
Входные данные
В первой строке входного файла находятся три натуральных числа: $N$ — количество занятых мест, $M$ — количество рядов и $K$ — количество мест в каждом ряду. В следующих $N$ строках находятся пары натуральных чисел: номер ряда и номер занятого места соответственно.
Гарантируется, что существует хотя бы одна подходящая четвёрка мест.
Выходные данные
В ответе запишите два целых числа: сначала наибольший номер ряда, затем количество подходящих четвёрок в этом ряду.
Типовой пример организации данных во входном файле
4 3 8
1 2
2 7
3 5
3 8
При таких исходных данных группа может разместиться во втором ряду на местах с 3-го по 6-е. Эти места свободны и в первом ряду. В третьем ряду подходящей четвёрки нет. Ответом является пара чисел 2 и 1.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
Система наблюдения ежеминутно фиксирует вход и выход сотрудников из офиса (в минутах, прошедших от начала суток). Считается, что в моменты фиксации входа и выхода сотрудник находится в офисе. Нулевая минута соответствует моменту начала рабочего дня в офисе, который работает 24 ч в сутки без перерыва.
Менеджер компании анализирует данные системы наблюдения за прошедшие сутки и выявляет непересекающиеся отрезки времени наибольшей длины, в течение которых число сотрудников, находящихся в офисе, не изменялось.
Определите минуту, когда в предпоследний раз за сутки число сотрудников поменялось, и укажите наибольшую длину отрезка времени, когда количество сотрудников оставалось неизменным.
Входные данные
В первой строке входного файла находится натуральное число $N$ ($N \le 100\thinspace 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-ю минуту, находился в офисе в течение этой минуты.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:
На автоматизированном складе смена робота должна непрерывно продолжаться с момента $S$ до момента $F$. Для питания робота можно использовать сменные аккумуляторные блоки. Каждый блок имеет известный промежуток работы: с момента $a$ до момента $b$, то есть может питать робота на интервале $[a; b)$.
В каждый момент времени должен быть подключён ровно один блок. Нужно выбрать минимальное количество блоков так, чтобы робот мог работать без перерыва на всём интервале $[S; F)$. Если таких способов несколько, выберите способ, при котором первый подключённый блок будет заменён как можно позже.
Входные данные
В первой строке входного файла находятся три натуральных числа $N$, $S$ и $F$: количество аккумуляторных блоков, момент начала смены и момент окончания смены. В следующих $N$ строках находятся пары натуральных чисел $a$ и $b$, задающие промежуток работы одного блока.
Гарантируется, что среди данных блоков можно обеспечить непрерывную работу робота на всём интервале $[S; F)$.
Выходные данные
В ответе запишите два целых числа: сначала минимальное количество блоков, затем длительность работы первого выбранного блока с момента $S$ до его замены.
Типовой пример организации данных во входном файле
6 10 30
8 15
10 20
16 25
19 27
25 32
27 31
При таких исходных данных достаточно трёх блоков: с промежутками работы [10; 20), [19; 27) и [25; 32). Первый блок используется с момента 10 до момента 20. Двух блоков недостаточно. Ответом является пара чисел 3 и 10.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
В кинотеатре известно, какие места уже забронированы зрителями. В каждом ряду места пронумерованы натуральными числами от $1$ до $1000$. Группе из $6$ человек нужно выделить подряд идущие свободные места в одном ряду.
Администратор рассматривает только такие варианты размещения, при которых в этом же ряду слева от группы есть хотя бы одно уже забронированное место, не обязательно соседнее с группой. Кроме того, справа от группы должно остаться хотя бы одно свободное место.
Нужно найти ряд с наибольшим номером, в котором можно разместить группу по этим правилам. Если в этом ряду есть несколько подходящих вариантов, выберите тот, в котором первое место группы имеет наибольший номер.
Входные данные
В первой строке входного файла находится число $N$ - количество уже забронированных мест. В следующих $N$ строках находятся пары натуральных чисел: номер ряда и номер места в этом ряду.
Гарантируется, что существует хотя бы один ряд, удовлетворяющий условию.
Выходные данные
В ответе запишите два целых числа: номер найденного ряда и номер первого места в группе из $6$ подряд идущих свободных мест.
Типовой пример организации данных во входном файле
4
3 1
3 998
4 2
4 998
При таких исходных данных выбирается ряд 4. Наибольший номер первого места группы равен 992: места с 992-го по 997-е свободны, слева есть забронированное место 2, а справа — свободное место 999. Ответом является пара чисел 4 и 992.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию:
Задание выполняется с использованием прилагаемого файла.
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 11:59:59.
Входные данные
Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1\thinspace 000\thinspace 000$) — количество строк в журнале и $K$ ($K < 1\thinspace 000\thinspace 000$) — вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1\thinspace 000\thinspace 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\thinspace 000\thinspace 000$) - количество строк в журнале и $K$ ($K < 1\thinspace 000\thinspace 000$) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: ($C < 1\thinspace 000\thinspace 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\thinspace 000\thinspace 000)$ — количество запросов и $K$ $(K<1\thinspace 000\thinspace 000)$ — вместимость раздела памяти в Кбайт. Каждая из следующих $N$ строк содержит время в формате ЧЧ:ММ:СС и два натуральных числа: $C$ $(C<1\thinspace 000\thinspace 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.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Файлы к заданию: