Задача к ЕГЭ по информатике на тему «Программирование - Обработка целочисленной информации с использованием сортировки» №3

Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и $N$ кусков оптоволокна, из которых попросили получить цельные куски по $M$ метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько цельных кусков получится и какова длина оставшейся части. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.

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

В первой строке входного файла записаны значения $N$ (количество кусков оптоволокна) и $M$ (длина необходимого цельного куска). Каждая из следующих $N$ строк содержит одно целое число – длину очередного куска.

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

Два числа: количество сварок в цельных кусках и количество кусков, из которых не сварить цельный кусок требуемой длины.

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

$10$ $30$

$17$

$15$

$14$

$12$

$11$

$8$

$6$

$5$

$4$

$2$

Сперва взяли $17$ и $14$ , обрез $1$ обратно в кучу $[15,12,11,8,6,5,4,2,1]$ – один кусок и 1 сварка. Затем взяли $15$ , $12$ и $4$ , обрез длиной $1$ обратно в кучу $[11,8,6,5,2,1,1]$ – еще один цельный кусок и 2 сварки. И затем взяли $11$ , $8$ , $6$ и $5$ , ровно $30$ , без обреза – еще кусок и 3 сварки. Осталось $[2,1,1]$ Итого: $6$ сварок и $3$ — количество оставшихся кусков, из которых не сварить цельный кусок нужной длины.

f = open(r"C:\Users\ТимофейDesktop\n2.txt")
n, dl = map(int, f.readline().split())
a = [int(x) for x in f.readlines()]
a.sort(reverse=True)
kolvo_svarok = 0
k = 0

while sum(a) >= dl:
    s = 0
    # собираем максимальные куски, кроме последнего
    while s + a[0] < dl:
        s += a[0]
        a.pop(0)
        kolvo_svarok += 1
    kolvo_svarok -= 1  # первый элемент мы не привариваем, а просто "берем в руки"
    # начинаем искать кусок, который дает минимальный обрезок
    ind = 0
    while ind < len(a) and s + a[ind] >= dl:
        ind += 1
    ind -= 1  # уменьшаем на один, потому что после while ind указывал на
       # предмаксимальный элемент, который можно добавить
    if s + a[ind] > dl:
        a.append(s + a[ind] - dl)  # добавляем обрезок
    kolvo_svarok += 1
    a.pop(ind)
    k += 1
    a.sort(reverse=True)
# в массиве a остались только куски, из которых не собрать цельный кусок (т.к. sum(a) < dl)
print(kolvo_svarok, len(a))

Ответ: 9421 530

Задача к ЕГЭ по информатике на тему «Программирование — Обработка целочисленной информации с использованием сортировки» №3