Школьник Петя готовится к ЕГЭ по нескольким предметам в разных онлайн школах. В каждой онлайн школе
уроки ведутся онлайн в определённое время. У Пети есть расписание всех уроков. Он хочет посетить как
можно больше уроков, при этом посещать уроки он хочет целиком. Ему не важно по какому предмету они
будут. Его интересует только количество посещённых уроков.
При этом он хочет сделать селфи и выложить его в интернет после первого просмотренного урока, и сделать
он это хочет, как можно быстрее. Поэтому, если будет несколько способов выбрать посещённые уроки, он
выберет тот способ, при котором конец первого урока будет раньше.
Входные данные
В первой строке файла находится натуральное число N – общее количество уроков. В следующих N строках
содержатся по два числа – время начала start, и время окончания end урока. Длительность урока: [start,
end).
Выходные данные
Выведите два числа – максимальное количество уроков, которые можно посетить и время селфи.
Типовой пример организации данных во входном файле
4
3 8
1 6
6 9
5 20
Ответ: 2 6.
Система наблюдения ежеминутно фиксирует вход и выход посетителей магазина (в минутах, прошедших от
начала суток). Считается, что в моменты фиксации входа и выхода посетитель находится в магазине. Нулевая
минута соответствует моменту открытия магазина, который работает 24 ч в сутки без перерыва. Менеджер
магазина анализирует данные системы наблюдения за прошедшие сутки, и выявляет отрезки времени наибольшей
длины, в течение которых число посетителей, находящихся в магазине, не изменялось. Далее менеджер
выбирает пики посещаемости — промежутки времени, когда количество посетителей в магазине было
наибольшим. Пиков посещаемости в течение суток может быть несколько.
Входные данные
Входной файл содержит время входа и выхода каждого посетителя магазина. Определите, сколько пиков
посещаемости было в течение суток, и укажите число посетителей в момент пика посещаемости.
Входные данные
В первой строке входного файла находится натуральное число N (N < 10000) - количество посетителей
магазина.
Следующие N строк содержат пары чисел, обозначающих соответственно время входа и время выхода посетителя
(все числа натуральные, не превышающие 1440).
Запишите в ответе два натуральных числа: сначала найденное количество пиков посещаемости, а затем число
посетителей в момент пика посещаемости.
Типовой пример организации данных во входном файле
6
10 50
100 150
110 155
120 160
130 170
151 170
При таких исходных данных было два пика посещаемости: в отрезки времени со 130 по 150 минуты и со 151 по
155 минуты. Число посетителей в момент пика посещаемости равно 4.
В отделении банка используется система распознавания лиц, с помощью которой фиксируется время, когда
посетитель пришел в отделение и время, когда он вышел. Для удобства, время хранится как целое число,
показывающее, сколько секунд прошло от начала суток до события. Известны данные о посетителях в течение
одних суток. Определите, сколько было промежутков времени, когда в отделении не было ни одного
посетителя. Под промежутком времени понимается интервал, в течении которого не было ни одного
посетителя, но за секунду до и через секунду после данного интервала посетители были.
Входные данные
В первой строке входного файла находится натуральное число N – количество посетителей (1 ≤ N ≤ 106). В
каждой из последующих N строк записаны через пробел в возрастающем порядке по два целых неотрицательных
числа t – время, в которое посетитель зашел в отделение и время, когда он вышел (0 ≤ t ≤ 86399).
Считается, что до начала суток и после их окончания в помещении посетителей не было. Все, кто зашел в
отделение, успел выйти до закрытия.
Выходные данные
Сначала количество временных промежутков, в течении которых не было ни одного посетителя, затем их
суммарная продолжительность.
На стадионе есть система предварительных заявок на покупку билетов на футбольный матч. Каждая заявка
содержит одно число – количество билетов, которые желает выкупить клиент.
Утром перед матчем оператор распределяет заявки по следующему алгоритму:
1) Все билеты в одной заявке должны быть в одном ряду,
2) В первую очередь подтверждаются заявки с наибольшим количеством забронированных мест,
3) Места проверяются в порядке следования рядов, то есть оператор старается разместить все места из
заявки в ряд с наименьшим номером. При этом максимально близко к началу ряда.
Определите, сколько заявок подтвердит оператор и сколько свободных мест останется на стадионе после
распределения всех заявок по описанному алгоритму.
Входные данные
В первой строке находится три числа: количество рядов на стадионе K, количество мест в одном ряду M и
количество заявок N. В каждой из N следующих строк находится одно число – количество билетов в заявке.
Выходные данные
Два числа – сначала количество подтвержденных заявок, затем количество оставшихся на стадионе мест.
Пример входных данных:
3 20 7
8
15
10
17
13
6
4
Для таких данных оператор удовлетворит 5 заявок – 15, 17, 13, 6 и 4. На стадионе останется 5 свободных
мест.
Системный администратор раз в неделю создаёт архив пользовательских файлов. Причем файлы размером больше
500 МБ записывает на диск D, а меньшего размера на диск E.
Известно, какой объём занимает файл каждого пользователя. Системный администратор старается сохранить
как можно больше файлов. Необходимо найти, сколько файлов на каждом диске может сохранить системный
администратор и максимальный размер сохраненного при данных условиях файла.
Входные данные
В первой строке входного файла находятся три числа: D – размер свободного места на диске D (натуральное
число, не превышающее 100 000), E – размер свободного места на диске E (натуральное число, не
превышающее 10 000) и N – общее количество файлов для сохранения (натуральное число, не превышающее
10000). В следующих N строках находятся значения объёмов файлов в МБ каждого пользователя (все числа
натуральные, не превышающие 5000), каждое в отдельной строке.
Запишите в ответе два числа: сначала число сохраненных файлов на обоих дисках, затем суммарный размер
самых больших по размеру файлов.
Пример входного файла:
3000 1000 6
300
350
400
1000
1500
2000
При таких исходных данных можно сохранить четыре файла – 350 и 400 (300 и 400) на диске E, 1000 и 2000
на диске D. Поэтому ответ должен содержать два числа – 4 и 2400.
Маркетплейс с оптового склада каждый день отправляет заказанные товары в точки выдачи. Маркетплейс имеет множество видов различных товаров, каждый из которых имеет какой-то вес. Для отправки склад выделяет транспорт таким образом, чтобы отправить все возможные типы товаров и при этом отправить как можно больше каждого из них, но не более, чем определённый вес S. Нужно определить, сколько всего товаров останется на складе и тип товара с самым большим остатком. Если таких товаров несколько, вывести товар с наименьшим кодом.
Входные данные:
В первой строке входного файла находится два числа через пробел: число N - количество доступных товаров (натуральное число, не превышающее 10000) и число S - вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 108). В следующих N строках находятся по два числа через пробел: тип товара (натуральное число, не превышающее 109) и его вес (натуральное число, не превышающее 105).
Известно, что видов товаров не бывает более тысячи.
Запишите в ответе два числа: сколько всего товаров останется на складе и тип товара с самым большим остатком.
Пример входного файла:
8 13
150 8
237 3
237 6
150 4
237 5
237 6
150 3
150 3
При таких исходных данных имеется всего два вида товаров ("150" и "237")
Товаров вида "150" можно погрузить три штуки (3, 3 и 4), останется 1 штука (8)
Товаров вида "237" можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6)
Поэтому ответ для приведённого примера: 3 237
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной
площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в
котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены
(заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию. В ответе запишите два целых
числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные
В первой строке входного файла находится одно число: N – количество занятых мест
(натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место
выкупленного билета (числа не превышают 100 000).
Выходные данные
Два целых неотрицательных числа: Максимальный номер ряда, где нашлись обозначенные в
задаче места и минимальный номер места.
Пример входных данных
6
50 12
60 157
60 160
60 22
60 25
Ответ: 60 23
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 10 000) и номер позиции в строке (целое число от 1 до 10 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.
Вам нужно определить наибольшую длину цепочки в одной строке, в которой светлые точки идут подряд. Если таких строк несколько, укажите номер первой из подходящих строк.
Входные данные
Входные данные представлены в файле следующим образом. В первой строке входного файла записано целое число N – количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.
Запишите в ответе два числа: сначала количество светлых точек в самой длинной цепочке из светлых точек, затем – номер строки, в которой находится эта цепочка (если таких строк несколько, запишите минимальный из их номеров).
Пример входного файла:
7
5 5
2 3
5 7
2 5
5 6
2 5
2 4
При таких исходных данных имеется две цепочки из светлых точек: в позициях 3, 4 и 5 строки 2, и в позициях 5, 6 и 7 строки 5. Обе они включают по 3 светлых точки, минимальный номер строки – 2. Ответ: 3 2.
Во дворце спорта идёт активная продажа билетов на предстоящий баскетбольный матч. Имеется информация об уже распределенных между болельщиками местах. При этом точно известно, что первое и последнее место в каждом из рядов занято. Хорошим называется такое место, что слева и справа от него есть ровно по 5 свободных мест. Найдите ряд с наибольшим номером, в котором есть хотя бы одно хорошее место, а также общее количество хороших мест во всех рядах.
Входные данные
В первой строке входного файла находится число N – количество занятых мест (натуральное число, не превышающее 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000: номер ряда и номер занятого места.
Выходные данные
Два целых неотрицательных числа: наибольший номер ряда, в котором есть хотя бы одно хорошее место, и общее количество хороших мест.
Типовой пример организации входных данных
11
5 1
20 30
5 7
20 18
5 30
20 1
20 4
20 16
5 13
20 10
20 24
Для данного примера подходит ряд 5, в котором слева и справа от 7 места есть ровно по 5 свободных мест, и ряд 20, в котором подходят 10-е и 24-е места. В ответ пойдёт ряд с наибольшим номером, содержащий хорошие места, и общее количество хороших мест. Ответ: 20 3.
В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть 100 000
рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение
товаров в чеке?
Входные данные
В первой строке входного файла находится число N – количество товаров в магазине (натуральное число, не
превышающее 10 000). В следующих N строках находятся числа, обозначающие цены товаров в рублях (все
числа чётные натуральные, не превышающие 10 000), каждое – в отдельной строке. Цены товаров указаны в
произвольном порядке.
Выходные данные
Запишите в ответе два целых числа: максимальное количество товаров, которое мог купить покупатель и
максимальное количество денег, которое могло у него остаться после покупки максимального количества
товаров.
Типовой пример организации данных во входном файле
5
4
80
30
50
40
Пример входного файла приведён, для покупателя со ста сорока рублями и для акции «каждый второй товар в
чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5 (Пример расположения
товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139), на второй вопрос число 1
(140 - 139 = 1).
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка
по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и
т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 11 единиц меньше длины
стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для
упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет
находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не
превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа
натуральные, не превышающие 10 000), каждое – в отдельной строке.
Выходные данные
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для
упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком
наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между
длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или
32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки
равна 32.
Брокерская контора решил разделить счета своих клиентов на обычный и премиум сегмент. Известен баланс
счёта каждого клиента. Маркетологи взяли эти данные и решили провести границу между двумя сегментами
таким образом, что в премиум сегменте окажется не менее 20% клиентов, и при этом разница наименьшего
размера счёта клиента из премиум сегмента и наибольшего размера счёта клиента из обычного сегмента
максимальна. Если таких максимальных разниц несколько, выбрать ту, при которой премиум клиентов
меньше.
Входные данные
В первой строке входного файла находится число N - количество открытых счетов (натуральное число, не
превышающее 10 000). В следующих N строках находится баланс каждого открытого счёта (натуральное число,
не превышающее 109).
Выходные данные
Запишите в ответе два числа: количество клиентов в премиум сегменте и наименьший размер счёта клиента из
этого сегмента.
Пример входного файла
7
200
550
800
1500
20
750
90
При таких входных данных очевидным премиальным счётом будет 1500, но нельзя включить в премиум сегмент
только его, потому что тогда он будет занимать менее 20% от всех счетов. Среди оставшихся разниц в
размере (70, 110, 350, 200 и 50) наибольшей является разница 350. Значит премиум сегмент будет содержать
4 счёта (за 550, 750, 800 и 1500). Поэтому ответ для приведённого примера: 4 550
Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и N кусков оптоволокна, из которых попросили получить цельные куски по M метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего сварок будет в цельных кусках и сколько метров уйдет в обрезку. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.
Входные данные:
В первой строке указаны N, M и в остальных строках размеры выданных кусков.
Например, для данных
10 30
17 15 14 12 11 8 6 5 4 2
Сперва взяли 17 и 14, обрез 1 обратно в кучу [15,12,11,8,6,5,4,2,1] - 1 сварка
Затем взяли 15,12 и 4, обрез 1 обратно в кучу [11,8,6,5,2,1,1] - 2 сварки
И затем взяли 11,8,6 и 5, ровно 30, без обреза – 3 сварки.
Итого 6 сварок и в сумме 2 (не штуки, а длины) обреза
Робот складывает монеты в ящики. Задача робота заполнить как можно большее количество ящиков монетами в количестве 100 штук. Роботу по конвейеру поступают корзины с монетами. В каждой корзине может быть от 1 до 99 монет.
Известно, что робот может высыпать в каждый ящик один раз содержимое не более двух корзин.
Необходимо написать программу, которая определяет, сколько ящиков можно заполнить ровно 100 монетами.
Входные данные представлены в файле следующим образом.
В первой строке записано число 1 < N < 10000 – количество корзин, в каждой из последующих N строк целое число 0 < K < 100 – количество монет в каждой корзине.
Выходные данные
В качестве ответа дать одно число – количество ящиков, заполненных 100 монетами.
Пример организации исходных данных во входном файле:
7
10
44
66
90
65
47
34
При таких исходных данных можно заполнить только 2 ящика по 100 монет 10 + 90 и 66 + 34.
Энтомолог Дмитрий занимается разведением редких видов бабочек. В день из кокона появляется одна особь вида «Павлиноглазка атлас». На выставке Дмитрий может продавать бабочек по различной цене, которая меняется каждый день, так же Дмитрию известна стоимость бабочки ближайшие N дней. Основываясь на известных данных, энтомолог рассчитал максимальное количество монет, которое он может заработать, если считать, что с первого дня у него в запасе была только одна бабочка.
Входные данные:
В первой строке входного файла находится число N – количество дней, в которые Дмитрию известна цена одной бабочки (натуральное число, не превышающее 10 000). В следующих N строках, на каждой строке находится стоимость одной бабочки в текущий день (все числа натуральные, не превышающие 10 000, каждое – в отдельной строке).
Запишите в ответе два целых числа: сначала максимальный заработок, который получил Дмитрий, действуя расчетливо. А затем запишите максимальную прибыль за один день, которую получил энтомолог.
Типовой пример организации во входном файле
5
32
13
85
52
46
При таких исходных данных, ответом будет являться пара чисел 353 255.
(3 * 85 + 52 + 46 = 353; 3 * 85 = 255)
На закупку товаров типов W и S выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров двух типов (по общему количеству). Если можно разными способами купить максимальное количество двух товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа S. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.
Определите, сколько будет закуплено товаров типа S и сколько денег останется.
Входные данные представлены в файле следующим образом.
Первая строка входного файла содержит два целых числа: N общее количество товаров и M сумма выделенных на закупку денег (в рублях).
Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква W или S), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.
Запишите в ответе два числа: сначала количество закупленных товаров типа S, затем оставшуюся неиспользованной сумму денег.