Информатика

(А. Богданов) Администратор написал скрипт для раскладки 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.

(А. Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Для каждой пары различных чисел из набора с чётной суммой вычисляется значение K -- наименьшая разница между средним арифметическим пары и каким-либо числом из набора. Необходимо определить количество пар чисел, для которых значение K равно 5, а также наименьшее из средних арифметических таких пар.

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

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

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

8
3
8
14
11
2
17
5
9

В примере рассмотрим пары со значением K равным одному. В данном случае есть 7 подходящих пар. Например, для пары (3;5) значение K равно 1 (минимальная разница среднего арифметического пары 4 и числа из набора равна 5 -- 4 = 1 ). В ответе надо записать числа 7 и 4.

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

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

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

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

8
3
8
14
11
2
17
5
9

В примере рассмотрим пары со значением K кратным трём. В данном случае есть 14 подходящих пар. Например, для пары (9, 17) значение K равно 6 (6 чисел из набора меньше среднего арифметического 13). В ответе надо записать числа 14 и 6.

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

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

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

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

6
3
8
14
11
2
17

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

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

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

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

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

6
3
8
14
11
2
17

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

(Е. Джобс) В магазине проводят акция -- каждый второй товар со скидкой 50%. При этом в акции участвуют только те товары, цены которых попадают в одну ценовую категорию. Каждая ценовая категория включает 500 целых значений: 1-500, 501-1000, 1001-1500 и т.д. Например, при наличии в чеке только позиций с ценами 300 и 1000 предложение акции не работает.

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

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

Пример входного файла (все значения с новой строки):

10
100 50 15 160 500 1002 2003 2010 2350 2400

При таких исходных данных ответ должен содержать 2 числа -- 2039 и 1005.

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

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

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

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

4 1000
A 14 12
Z 30 7
A 40 20
Z 50 15

В данном случае сначала нужно купить изделия A: 12 изделий по 14 рублей и 20 изделий по 40 рублей. На это будет потрачено 968 рублей. На оставшиеся 32 рубля можно купить 1 изделие Z по 30 рублей. Таким образом, всего будет куплено 1 изделие Z и останется 2 рубля. В ответе надо записать числа 1 и 2.

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

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

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

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

4 1000
A 14 12
Z 30 7
A 40 24
Z 50 15

В данном случае сначала нужно купить изделия Z: 7 изделий по 30 рублей и 15 изделий по 50 рублей. На это будет потрачено 960 рублей. На оставшиеся 40 рублей можно купить 2 изделия A по 14 рублей. Таким образом, всего будет куплено 2 изделия A и останется 12 рублей. В ответе надо записать числа 2 и 12.

(Е. Джобс) Системный администратор раз в неделю создаёт архив пользовательских файлов. Причем файлы размером больше 500 МБ записывает на диск D, а меньшего размера на диск E. Известно, какой объём занимает файл каждого пользователя. Системный администратор старается сохранить как можно больше файлов. Необходимо найти, сколько файлов на каждом диске может сохранить системный администратор и максимальный размер сохраненного при данных условиях файла для каждого диска.

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

Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 310 до 320 кг включительно грузят в первую очередь, выбирая грузы по убыванию массы, начиная с самого тяжёлого. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.

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

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

6 720
100
315
120
160
140
300

В данном случае сначала нужно взять груз массой 315 кг. Остается 405 кг. После этого можно вывезти ещё максимум 3 груза. Это можно сделать тремя способами: 100 + 120 + 140, 100 + 140 + 160, 100 + 120 + 160. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов два: 100 + 120 + 160, 100 + 140 + 160. Из этих способов выбираем тот, при котором больше масса второго по величине груза, то есть 100 + 140 + 160. Всего получается 4 груза общей массой 715 кг. Ответ: 4 715.

Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 180 до 200 кг включительно грузят в первую очередь, выбирая грузы по убыванию массы, начиная с самого тяжёлого. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.

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

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

6 700
100
185
120
160
140
300

В данном случае сначала нужно взять груз массой 185 кг. Остается 515 кг. После этого можно вывезти ещё максимум 3 груза. Это можно сделать четырьмя способами: 100 + 120 + 140, 100 + 140 + 160, 100 + 120 + 160, 120 + 140 + 160. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов три: 100 + 120 + 160, 100 + 140 + 160, 120 + 140 + 160. Из этих способов выбираем те, при которых больше масса второго по величине груза, то есть 100 + 140 + 160 и 120 + 140 + 160. Их них нужно выбрать вариант 120 + 140 + 160, так как в этом случае третий по величине груз наиболее тяжёлый. Всего получается 4 груза общей массой 605 кг. Ответ: 4 605.

(Е. Джобс) Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. Администратор сохраняет файлы по следующему правилу: выбирается файл максимального размера, который может быть записан на диск, затем выбирается файл минимального размера, который может быть записан на диск. Данный сценарий повторяется до тех пор, пока на диск нельзя будет записать ни одного из оставшихся файлов.

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

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

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

100 5
80
30
10
5
7

При таких исходных данных можно сохранить файлы трех пользователей. Объёмы этих трёх файлов 80, 5 и 10. Последний выбранный файл имеет размер 10 , поэтому ответ для приведённого примера: 3 10.

(А.М. Кабанов) На складе лежат пакеты с углём различного веса и стоимости. Вес и стоимость записаны на каждом пакете как натуральные числа: вес не превосходит 100, стоимость не превосходит 10000. Для транспортировки отбираются K пакетов с самой низкой ценой угля за единицу веса; при равной стоимости за единицу веса выбираются пакеты с большим весом. По заданной информации о пакетах с углём и количестве транспортируемых пакетов определите суммарный вес угля в отправленных пакетах и стоимость самого тяжёлого отправленного пакета.

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

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

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

10 4
47 470
50 600
60 480
45 540
30 300
15 180
70 560
30 360
91 910
40 320

При таких исходных данных самая низкая стоимость угля в пакетах весом 60, 70, 40; затем -- у пакетов весом 91, 30, 47. Поэтому наибольший возможный вес к отправке равен 70+60+40+91 = 261, а стоимость самого тяжёлого отправленного пакета равна 910.