g1shy
@g1shy
Young python learner

Как решить эту задачу(ЕГЭ информатика 2021)?

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

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

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

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

Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50

Всё, на что у меня хватило сил, это найти максимальное число пользователей:
spoiler
и то неправильно

f = open("zadanie26_var_1.txt")
s = list(f)
k = 0
for i in range(int(s[1]), len(s)):
    if s[i] + s[i+1] <= s[0]:
        k+=1
        print(k)


Хелпаните, ребят! Буду рад любой подсказке, которая поможет сдвинуть процесс решения с одного места.
  • Вопрос задан
  • 362 просмотра
Пригласить эксперта
Ответы на вопрос 2
trapwalker
@trapwalker Куратор тега Python
Программист, энтузиаст
Тут задачки постить запрещено, но какой-то код вы предложили, хотя и неправильный, поэтому заслужили подсказку. Вам бы я осоветовал не код сперва писать, а порассуждать о том как собираетесь решать задачу. Придумайте алгоритм сначала на русском языке в свободной форме. У вас нет никакого опыта, поэтому язык программирования вас слишком сильно отвлекает от сути задачи.

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

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

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

Давайте я вам ещё рефакторинг вашего кода сделаю. Это не сделает его правильным, но он станет лучше.
with open("zadanie26_var_1.txt") as f:  # Так открытый файл будет закрыт после считывания
    # Так вы считаете первые два числа в отдельные переменные:
    total_volume, users_count = map(int, f.readline().strip().split())
    # А так считаете остальные строки в список и нечаянные пустые строки вас не смутят:
    user_sizes = [int(line.strip()) for line in f if line]  

# Хорошо бы вынести логику решения в отдельную функцию:
def solve(s, n, lst):
    # Вот так можно сделать проверки корректности (ну чисто для себя) входных данных:
    assert s <= 10000, 'Invalid total volume'
    assert len(lst) == n, 'Users count is not valid.'
    assert n <= 2000, 'Wrong users count.'
    assert all(0 < x <= 100 for x in lst), 'Invalid user size.'

    # Вот здесь вот вы сделаете нужные вычисления ;)
    backup_users_count = ...
    max_backup_file_size = ...

    return backup_users_count, max_backup_file_size

# Ну а вызвать функцию и напечатать ее результат вы тоже сумеете, правда?
Ответ написан
milssky
@milssky
Координатор племени фиолетовых обезьянок
Так или иначе, эти задачи связаны с сортировками.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы