26.04 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и 
кусков оптоволокна, из
которых попросили получить цельные куски по 
метров. С целью снижения затухания сигнала в полученном кабеле
нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько цельных кусков
получится и какова длина оставшейся части. Ваня выбирал куски строго по уменьшению длины, за исключением
последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для
следующего использования.
Входные данные
В первой строке входного файла записаны значения 
(количество кусков оптоволокна) и 
(длина
необходимого цельного куска). Каждая из следующих 
строк содержит одно целое число – длину очередного
куска.
Выходные данные
Два числа: количество сварок в цельных кусках и количество кусков, из которых не сварить цельный кусок требуемой длины.
Пример входного файла:
Сперва взяли 
и 
, обрез 
обратно в кучу ![[15,12,11,8,6,5,4,2,1]](/api/latex-service/v1/GetSession/55930/index-959c33bab19c7f39dd08cd4eb9aff26b.svg)
– один кусок и 1 сварка. Затем взяли 
, 
и 
, обрез длиной 
обратно в кучу ![[11,8,6,5,2,1,1]](/api/latex-service/v1/GetSession/55930/index-24f03fb3a639aaf0afa2862ea66f79e6.svg)
– еще один цельный кусок и 2 сварки. И затем взяли 
, 
, 
и
, ровно 
, без обреза – еще кусок и 3 сварки. Осталось ![[2,1,1]](/api/latex-service/v1/GetSession/55930/index-79ad580a775d910920b66c6a9282fb25.svg)
Итого: 
сварок и 
- количество оставшихся кусков,
из которых не сварить цельный кусок нужной длины.
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))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
