Задача к ЕГЭ по информатике на тему «Архив пользовательских файлов» №1

Задание выполняется с использованием прилагаемых файлов

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

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

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

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

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

Пример входных данных:

$200 4$

$90$

$30$

$100$

$80$

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

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Первые два числа ( $S$ и $N$ ) вставим правее в ячейки С1 и D1, чтобы было удобнее. Отфильтруем столбец А по возрастанию. С помощью кнопок shift + вниз из ячейки А1 будем двигаться вниз, пока сумма в правом нижнем углу будет меньше $9999$ . Получим, что наибольшее число пользователей, чьи файлы могут быть помещены в архив, равно $762$ . Для удобства переместим всех $762$ пользователей в столбец В. Теперь вычислим, сколько свободного места осталось на диске. Для этого в ячейку D762 запишем формулу =C1-СУММ(B1:B3236). Получим, что оставшееся место на диске равно $13$ . Текущий максимальный размер файла, который поместится в архив, равен числу в ячейке В762, это $24$ . Тогда максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей, равен $24 +13$ , то есть $37$ . Проверяем, действительно, в ячейке А1195 есть число $37$ . Переместим его в столбец В, а число, записанное в ячейке В762, переместим обратно в столбец А. Теперь разница в ячейке D762 между максимальной суммой и суммой выбранных чисел равна $0$ , значит, никакое число больше $37$ взять не получится.

Решение 2 (Python):

file = open("Задание_26__d0r7.txt")
lines = file.readlines()

s, n = map(int, lines[0].split())
array = list(map(int, lines[1:]))
array = sorted(array)

i = 0
current_sum = 0
last_elem = 0
ind_last = 0
users_count = 0

while i < n - 1:
    if current_sum + array[i] <= s:
        current_sum += array[i]
        users_count += 1
        last_elem = array[i]
        ind_last = i
    i += 1

free_space = s - current_sum
t = last_elem + free_space
replacing_last = 0

for i in range(ind_last, n):
    if array[i] <= t:
        replacing_last = array[i]

print(users_count, replacing_last)

Ответ: 762 37