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

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

Задача 1#25786

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

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

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

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

В первой строке входного файла находятся два числа: 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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