Информатика

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

Входные данные представлены в файле 26-69.txt следующим образом. В первой строке входного файла записано одно число: 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.

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

-- необходимо удалить как можно больше супервирусов;

-- нельзя удалять два и более супервируса подряд;

-- нельзя удалять супервирус последним;

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

Входные данные представлены в файле 26-68.txt следующим образом. Первая строка входного файла содержит количество записей N и общее время T, отведённое на удаление этих вирусов. Каждая из следующих N строк содержит два целых числа: уровень опасности вируса и время, которое требуется для его удаления.

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

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

5 50
7 13
9 20
4 3
8 9
5 5

Средний уровень опасности равен 6.6, значит, суперопасными считаются вирусы с уровнем опасности >= 7. Удаляем сначала супервирус 8-9, далее обычный вирус 4-3, потом снова суперопасный 7-13, затем обычный 5-5. Обычных вирусов не осталось, значит, суперопасные тоже удалять нельзя. Итого удалено 4 вируса. На удаление супервирусов затрачено времени 9 + 13 = 22. Ответ: 4 22.

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

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

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

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

6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400

В данном случае наименьшее число запросов (2) выполнялось в интервале времени между 1000 и 1300, между 3700 и 5000, а также от 5700 до 6000 (общее время 300 + 1300 + 300 = 1900). Ответ: 2 1900.

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

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

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

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

6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400

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

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

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

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

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

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

6 110
40 E
50 A
50 B
30 C
20 B
10 A

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

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

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

Входные данные представлены в файле 26-64.txt следующим образом. Первая строка входного файла содержит два целых числа: 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 и сколько денег останется.

Входные данные представлены в файле 26-62.txt следующим образом. Первая строка входного файла содержит два целых числа: 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.

(Л. Шастин) Полина хранит на компьютере картинки и видео различного размера. Она хочет поместить как можно больше картинок и видео на флеш-накопитель, объём которого равен M Кбайт. Сначала она сохраняет самые маленькие видеозаписи до тех пор, пока они не займут не менее половины от общей памяти. В оставшееся место Полина сохраняет как можно больше картинок, стремясь занять весь оставшийся объём. Определите максимальное количество файлов (картинок и видео), которое Полина может сохранить на флеш-накопителе, и максимальный объём сохранённой картинки.

Входные данные представлены в файле 26-61.txt следующим образом. В первой строке записаны два числа: N -- количество всех изображений и видео, M -- объём флеш-накопителя (N и M -- натуральные числа, не превышающие 10⁶). В следующих N строках находятся значения объёмов картинок и видео в Кбайтах. Информационный объём каждой картинки не более 100 Кбайт, объём видео -- не менее 101 Кбайт.

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

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

8 150
20
101
15
400
5
900
10
9

При таких исходных данных можно сохранить 4 картинки и 1 видео объёмом 101, всего 4 + 1 = 5 элементов. При этом максимальный объём сохранённой картинки равен 20 (например, 20+10+9+5). Ответ: 5 20.

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

Входные данные представлены в файле 26-60.txt следующим образом. В первой строке через пробел записаны два целых числа K и N. В следующих K строках записано по одному числу -- количеством мест по каждой специальности. Следующие N строк содержат пары чисел: баллы студента (до 300 включительно) и код выбранной специальности (начиная с 0).

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

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

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

В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.

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

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.

(А. Комков) Магазин «1000 мелочей» закупает у поставщика продукцию для дальнейшей перепродажи. Известно количество товаров на складе у поставщика и стоимость каждого из них. К сожалению, бюджет магазина ограничен, поэтому принято решение закупить как можно больше товаров на ту сумму, которой располагает магазин, причем закупают не менее двух товаров с каждой ценой. По заданной информации о цене каждого товара и бюджете магазина, определите

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

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

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

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

100 9
20
30
20
5
10
15
10
30
10

В данном примере можно закупиться следующим образом: 10 10 10 20 20, либо 10 10 10 30 30. В первом случае максимальная стоимость товара будет 20, а во втором -- 30. Наибольшее количество товаров с одинаковой ценой в обоих случаях равно 3. В ответе нужно указать: 30 3.

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

Входные данные представлены в файле 26-57.txt следующим образом. В первой строке входного файла записаны значения N (количество кусков оптоволокна) и M (длина необходимого цельного куска). Каждая из следующих N строк содержит одно целое число -- длину очередного куска.

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

10 30
17 15 14 12 11 8 6 5 4 2

Сперва взяли 17 и 14, обрез 1 обратно в кучу \[15,12,11,8,6,5,4,2,1\] -- одна сварка. Затем взяли 15,12 и 4, обрез длиной 1 обратно в кучу \[11,8,6,5,2,1,1\] -- две сварки. И затем взяли 11,8,6 и 5, ровно 30, без обреза -- три сварки. Итого: 6 сварок и 3 оставшихся куска оптоволокна.

(А. Богданов) Администратор написал скрипт для раскладки N архивов на K дисков, каждый объемом V. Алгоритм скрипта обрабатывает файлы в порядке убывания их размера. Если файл помещается на диск, то следующий по размеру файл стараются поместить на следующий диск. Если не помещается, то на следующий, и так по кругу. Если файл не поместился ни на один диск, то он откладывается в локальную папку. Укажите в ответе два числа: объем всех отложенных файлов и их количество.

Входные данные представлены в файле 26-56.txt следующим образом. В первой строке входного файла записаны значения V (объём диска), K (количество дисков) и N (количество архивов). Каждая из следующих N строк содержит одно целое число -- размер очередного архива.

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

20 3 10
17
15
13
12
11
7
6
4
3
2

При таких входных данных ответ будет 31 и 4: в локальную папку отложены архивы размером 12, 11, 6 и 2.

(Е. Джобс) Для перевозки партии грузов различной массы выкупают место у компании, которая организует перевозку на грузовых судах. Судно не может принять на борт больше S тонн груза. Известно, что отдельный груз нельзя разделить для перевозки, то есть один груз должен доставляться одним рейсом на одном грузовом судне. В первую очередь перевозятся грузы как можно большей массы. За какое минимальное количество рейсов можно перевезти все грузы?

В ответе запишите два числа -- минимальное количество рейсов и суммарную массу грузов, которые будут перевезены последним рейсом.

Входные данные представлены в файле 26-55.txt следующим образом. В первой строке входного файла записаны два целых числа: N -- общее количество грузов и S -- грузоподъёмность судна в тоннах. Каждая из следующих N строк содержит одно целое число \< S -- массу груза в тоннах.

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

6 500
140
150
160
200
220
240

Первым рейсом будет отправлено 2 груза -- 240 и 220, вторым -- 200, 160 и 140, третьим -- 150. При таких входных данных ответ будет 3 и 150.

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

Входные данные представлены в файле 26-53.txt следующим образом. Первая строка содержит целое число N -- общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10⁹.

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

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

6
3
8
14
11
2
17

В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11) и 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 8.

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

Входные данные представлены в файле 26-53.txt следующим образом. Первая строка содержит целое число N -- общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10⁹.

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

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

6
3
8
14
7
9
11

В данном случае есть три подходящие пары: 3 и 11 (среднее арифметическое 7), 7 и 9 (среднее арифметическое 8), 7 и 11 (среднее арифметическое 9). В ответе надо записать числа 3 и 9.

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

Входные данные представлены в файле 26-52.txt следующим образом. Первая строка содержит целое число N -- общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10⁹.

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

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

8
3
8
14
11
2
16
5
9

В примере рассмотрим пары, между которыми помещаются не более 3 чисел из набора. В данном случае есть три подходящие пары: 2 и 8, 9 и 11, 14 и 16. В ответе надо записать числа 3 и 5.

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

Входные данные представлены в файле 26-51.txt следующим образом. Первая строка содержит целое число N -- общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10⁹.

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

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

8
3
8
14
11
2
16
5
9

В примере рассмотрим пары, между которыми помещаются не менее 3 чисел из набора. В данном случае есть четыре подходящие пары: 2 и 14, 2 и 16, 3 и 11, 8 и 16. В ответе надо записать числа 4 и 12.

(А. Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары с чётной суммой, такие что:

- хотя бы половина чисел набора меньше среднего арифметического пары

- хотя бы четверть чисел набора больше среднего арифметического пары,

Определите количество таких пар и наименьшее из средних арифметических таких пар.

Входные данные представлены в файле 26-50.txt следующим образом. Первая строка содержит целое число N -- общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10⁹.

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

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

8
3
8
14
11
2
16
5
9

В данном случае есть четыре подходящие пары: 2 и 16 (среднее арифметическое 9), 8 и 14 (среднее арифметическое 11), 9 и 11 (среднее арифметическое 10), 8 и 16 (среднее арифметическое 12). В ответе надо записать числа 4 и 9.

(А. Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары чисел с чётной суммой, такие что хотя бы половина элементов последовательности больше, чем среднее арифметическое элементов пары. Необходимо определить, сколько в наборе таких пар, и наибольшее из средних арифметических таких пар.

Входные данные представлены в файле 26-49.txt следующим образом. Первая строка содержит целое число N -- общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10⁹.

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

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

6
3
8
14
11
2
17

В данном случае есть четыре подходящие пары: 2 и 8 (среднее арифметическое 5), 2 и 14 (среднее арифметическое 8), 3 и 11 (среднее арифметическое 7), 3 и 17 (среднее арифметическое 10). В ответе надо записать числа 4 и 10.