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

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

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

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

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

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

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

$100 4$

$80$

$30$

$10$

$5$

При таких входных данных, ответ будет: $3 10$

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Всего чисел у нас $1000$ .

Отсортируем числа в изначальном столбце по возрастанию. Далее распределим на $2$ колонки таким способом:

$1$ колонку строчки от $1$ до $500$ оставляем на месте, а $501$ и до $1000$ копируем и вставляем в столбец B.

Далее столбец B сортируем по убыванию.

Весь объем у нас диска составляет $100000$ . Поэтому выделяем ячейки до той степени, пока минимально не превысим это число.

Мы остановились на $287$ строке и сумма будет $100092$ . Но если не брать самый маленький файл — $120$ , то $100092− 120 < 100000$ . Значит мы возьмем последний файл $229$ и всего файлов, которые мы возьмем, будет $573$ .

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

file = open("Задание_26.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
min_files = array[:n // 2 + (n % 2)]  # массив, содержащий первые n//2 + (n % 2) элементов
max_files = array[n // 2 + (n % 2):][::-1]  # массив, содержащий максимальные n//2 элементов
                                            # от максимального (n) к минимальному (n // 2 + (n % 2))
flag = True # флаг позволит нам не посчитать подряд два минимальных файла, такая ситуация может
            # возникнуть в конце, когда место в архиве еще есть, мы положим в него маленький
            # файлик, и останется еще место, в которое уже невозможно положить минимальный из
            # максимальных, но маленький файлик еще положить можно, но по условию нам так
            # делать нельзя

while i != n // 2 + n % 2:
    if current_sum + min_files[i] <= s and flag:
        current_sum += min_files[i]
        users_count += 1
        last_elem = array[i]
        ind_last = i
        flag = False
    if i != len(max_files) and current_sum + max_files[i] <= s and flag == False:
        current_sum += max_files[i]
        users_count += 1
        last_elem = array[i]
        ind_last = i
        flag = True
    i += 1

if flag == False and ind_last != len(max_files) and 
        current_sum - last_elem + max_files[ind_last] <= s:












































































































































































































    last_elem = max_files[ind_last]

print(users_count, last_elem)

Ответ: 573 229