Тема 26. Программирование - Обработка целочисленной информации с использованием сортировки
26.03 Архив пользовательских файлов
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование - обработка целочисленной информации с использованием сортировки
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#24621

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

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

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

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

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

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

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

1605

40

80

30

70

50

При таких исходных данных мы можем сохранить максимум 3  пользователей. Это будут пользователи со следующим объемом данных: 80,50 и 30  . Сумма наибольшего и наименьшего будет равна 80+ 30 = 110  . Ответ: 3110  .

Вложения к задаче
Показать ответ и решение

Решение 1 ( Excel / LibreOffice):
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения размера архива и кол-ва пользователей куда-нибудь, где они нам не помешают. Сортируем числа по возрастанию, так как именно таким образом мы добавим в архив максимальное количество. Максимально заполняем наш архив, размер которого равен 6000. Для удобства все файлы, которые можно поместить в архив, перенесем в отдельный столбик, например в B  . Получаем сумму 5980. А вдруг можно получить больше? Проверим это, убрав последний элемент обратно в столбик A  . Теперь сумма размеров выбранных файлов равна 5955. Посмотрим, есть ли среди неиспользованных нами файлов такие, значение которых максимально приближено к числу 45 (6000 - 5955), но не больше него. Максимальное число, которое мы можем положить в архив - 45. Значит, переносим его в столбик B  и считаем ответ.

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

file = open("Задание_26-2__mpyq.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 + array[0])

Ответ: 466 46

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!