Задание 26 ЕГЭ по информатике

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

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

Типовой пример организации данных во входном файле
5 50
10 39
15 35
12 25
30 41
45 48

При таких исходных данных три участка являются "непригодными": 1-9, 42-44, 49-50. Длина наибольшего из уже отремонтированных участков равна 31 (10-41). Ответ: 3 31.

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

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

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

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

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

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

7

1 2

2 3

3 6

2 4

1 3

2 5

2 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6

1 1

1 2

1 3

1 5

1 6

1 7

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

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

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

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

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

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

6

1 1

1 2

1 3

1 4

1 5

1 6

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

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

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

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

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

5

7

1

3

14

1

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

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

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

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

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

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

7

4858

112

4858

4858

31

112

4858

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

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

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

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

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

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

10

1962 1

1962 2

1962 3

1962 4

1962 6

1962 7

1962 8

1963 4

1964 1

1964 3

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

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

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

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

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

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

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

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

1200 100 3

430 300

200 150

900 50

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

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

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

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

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

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

7

200

550

800

1500

20

750

90

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

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

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

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

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

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

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

8 13

150 8

237 3

237 6

150 4

237 5

237 6

150 3

150 3

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

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

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

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

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

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

Типовой пример организации данных во входном файле
7 3
100 20
200 55
150 50
700 50
50 80
125 88
800 80

При таких исходных данных организация купит товары {125, 88}, {800, 80} и {700, 50} со скидкой. Ответ: 1025 125.

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

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

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

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

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

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

4

8

1

3

1

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

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

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

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

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

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

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

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

11000 8

200

3800

3500

500

3100

800

4100

2500

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

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

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

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

10

5 5

5 6

5 7

16 9

16 3

16 6

20 23

20 28

20 29

20 30

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

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

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

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

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

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

5 2

220

210

210

200

195

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

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

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

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

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

6 1000

1300 2200

0 3700

1300 5700

0 0

5000 0

1800 3400

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

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

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

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

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

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

7

10 40

50 130

70 130

75 90

120 170

140 170

150 180

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

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

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

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

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

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

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

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

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

100 5

80 A

30 B

20 B

40 A

40 В

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

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

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

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

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

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

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

7 12

150 8

237 3

150 4

237 5

237 5

150 3

150 3

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

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

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

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

5 18

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

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

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

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

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

6 110

40 E

50 A

50 D

30 C

20 B

10 A

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

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

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

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

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

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

6 110

40 Z

50 Q

50 Z

30 Z

20 Q

10 Z

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

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

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

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

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

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

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

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

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

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

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

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

8 150

20

101

15

400

5

900

10

9

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

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

Ответ: 0 5.

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

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

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

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

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

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

10

5 5

5 9

5 6

16 9

16 3

16 6

20 23

20 28

20 35

20 40

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

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

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

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

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

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

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

10 30

17 15 14 12 11 8 6 5 4 2

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

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

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

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

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

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

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

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

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

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

100 5

80

30

50

40

20

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