Задача к ЕГЭ по информатике на тему «прочие прототипы» №3

Игорь Владимирович хранит на компьютере картинки и видео различного размера. Он хочет поместить как можно больше картинок и видео на флеш-накопитель, объём которого равен $K$ Кбайт, причём так, чтобы не менее чем половина его объёма была зарезервирована под видео. Определите максимальное количество файлов (картинок и видео), которое Игорь Владимирович может сохранить на флеш-накопителе, и максимальный объём сохранённого видео. Информационный объем каждой картинки не более $50$ Кбайт, а объем видео – не менее $51$ Кбайт.

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

Входные данные представлены в файле следующим образом. В первой строке записаны два числа: $N$ — количество всех изображений и видео, $K$ — объём флеш-накопителя. В следующих $N$ строках находятся значения объёмов картинок и видео в Кбайтах.

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

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

$8 150$

$20$

$101$

$15$

$400$

$5$

$900$

$10$

$9$

Ответ для приведённого примера:

$5 20$

Решение 1 ( Excel / LibreOffice):

Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значения количества изображений и видео и объема флеш-накопителя, где они нам не помешают. Сортируем числа по возрастанию. В условии нам сказано, что файлы, объем которых меньше либо равен 50 Кбайт, являются изображениями, тогда остальные — видео. Перенесем все видео в другой столбик, например в $B$ . Не менее половины объема памяти флеш-накопителя ОБЯЗАТЕЛЬНО должны занимать видео, значит, найдем половину всей памяти нашей флешки и возьмем максимальное кол-во видео, чтобы ТОЧНО заполнить это место, перенес их в столбик $C$ . Оставшееся место заполним изображениями, имеющими минимальный объем. Изображений больше нет, а место осталось, значит, добавляем еще видео (для удобства перенесем их в столбик $D$ ). Теперь у нас осталось 376 КБ. А вдруг можно получить больше? Проверим это, убрав последний элемент обратно в столбик $B$ . Теперь сумма размеров выбранных файлов равна 554207. Проверим, нет ли у нас в столбике $A$ числа, максимально близкого к 793 (555000-554207=793)? У нас есть число 793!!! Значит, переносим его в столбик $D$ и считаем ответ.

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

file = open("2.txt")
lines = file.readlines()

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

images = 0
videos = 0
i = 0

while array[i] <= 50:
    i += 1

while videos + array[i] <= k // 2:
    videos += array[i]
    i += 1

videos += array[i]
max_elem = array[i]

for j in range(len(array)):
    if array[j] <= 50 and images + videos + array[j] <= k:
        images += array[j]

i += 1
free_space = k - (images + videos)

if free_space > max_elem:
    while free_space > 0:
        if free_space - array[i] < 0:
            break
        free_space -= array[i]
        max_elem = array[i]
        i += 1
        if i >= len(array):
            break













































































































































































































free_space += max_elem

for j in range(len(array) - 1, i - 1, -1):
    print(array[j])
    if array[j] <= free_space:
        max_elem = array[j]
        break

print(i, max_elem)

Ответ: 9343 793