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

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

Просмотров 8 Комментарии 0

Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и $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]$ — одна сварка. Затем взяли $15$ , $12$ и $4$ , обрез длиной $1$ обратно в кучу $[11,8,6,5,2,1,1]$ — две сварки. И затем взяли $11$ , $8$ , $6$ и $5$ , ровно $30$ , без обреза — три сварки. Итого: $6$ сварок и $3$ оставшихся куска оптоволокна. Ответ: $6 3.$

file = open("Задание_26__ra53.txt")

n, m = [int(i) for i in file.readline().split()]
a = [int(file.readline()) for j in range(n)]
for i in range(100):
    a.append(0)
a.sort(reverse=True)
svarki = 0
while a[0] > 0:
    s = 0
    i = 0
    while s < m:
        if i >= len(a):
            print(svarki, len(a) - a.count(0))
            exit()
        s = s + a[i]
        i += 1
    for j in range(i - 1):
        a[j] = 0
    last = a[i - 1]
    svarki += i - 1
    last_ind = i - 1
    s -= last
    while i < len(a):
        if s + a[i] >= m:
            last = a[i]
            last_ind = i
        i += 1
    a[last_ind] = s + last - m
    a.sort(reverse=True)

Ответ: 9421 530