Отправлено: 17.01.22 23:43. Заголовок: Задача (№ 4205) (А. Богданов)

Не сходится ответ в задаче (№ 4205) (А. Богданов), в чем может быть ошибка?

Условие
Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и N кусков оптоволокна, из которых попросили получить цельные куски по M метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего сварок будет в цельных кусках и сколько останется кусков, из которых не сварить цельный кусок требуемой длины. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.
Входные данные представлены в файле 26-57.txt следующим образом. В первой строке входного файла записаны значения 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 оставшихся куска оптоволокна.

Ответ: 7380 285
Я получаю результат: 7431 161


Код программы на Python:

 
 # Бинарный поиск подходящего куска оптоволокна 
 # cuts_list - массив кусков оптоволокна, должен быть отсортирован по возрастанию 
 # min_cut_len - минимальная необходимая длина куска оптоволокна 
 def find_suitable_cut(cuts_list, min_cut_len): 
     index_start = 0                 # Левая граница 
     index_end = len(cuts_list) - 1  # Правая граница 
     suitable_cut_index = index_end  # Индекс подходящего куска оптоволокна, по умолчанию самый большой 
  
     # Продолжать поиск пока границы не сойдутся 
     while index_start <= index_end: 
         # На левой границе кусок точно подходящей длины 
         if min_cut_len == cuts_list[index_start]: 
             return index_start 
         # На правой границе кусок точно подходящей длины 
         if min_cut_len == cuts_list[index_end]: 
             return index_end 
  
         # Если минимальная необходимая длина куска оптоволокна меньше куска на левой границе, 
         # то индекс подходящего отрезка переместить на левую границу 
         if (min_cut_len <= cuts_list[index_start]) and (suitable_cut_index != index_start): 
             suitable_cut_index = index_start 
  
         # Срейдний индекс 
         index_mid = (index_start + index_end) // 2 
         # Если необходимый кусок находится левее середины, то сдвинуть правую границу 
         if min_cut_len < cuts_list[index_mid]: 
             index_end = index_mid - 1 
         # Если необходимый кусок находится правее середины, то сдвинуть левую границу 
         elif min_cut_len > cuts_list[index_mid]: 
             index_start = index_mid + 1 
         # Ровно по середине находится кусок точно подходящей длины 
         else: 
             return index_mid 
  
     # Вернуть индекс подходящего куска оптоволокна, если не нашелся кусок точной длины 
     return suitable_cut_index 
  
  
 f = open('26_2.txt') 
 lines = f.readlines() 
 f.close() 
 target_length = int(lines[0].split(' ')[1])  # Необходимая длина оптоволокна 
 cuts = [int(i) for i in lines[1:]]           # Массив кусков оптоволокна 
 cuts.sort()                                  # Сортировка кусков по возрастанию 
 cuts_length = sum(cuts)                      # Сумма длин всех кусков оптоволокна 
 weldings = 0                                 # Общее количество сварок 
 count = 0                                    # Количество полученных кусков требуемой длины 
  
 # Подсчет оптоволокна 
 while cuts_length >= target_length: 
     used_cuts_length = cuts.pop()  # Длина использованных кусков оптоволокна (берётся последний, самый длинный) 
     used_cuts = 1                  # Количество использованных кусков оптоволокна 
  
     # Подсчет необходимого количества кусков оптоволокна для требуемой длины 
     while used_cuts_length < target_length: 
         index = find_suitable_cut(cuts, target_length - used_cuts_length)  # Поиск индекса подходящего куска 
         used_cuts_length += cuts.pop(index)                                # Добавить найденный кусок оптоволокна 
         used_cuts += 1                                                     # Инкремент кусков оптоволокна 
  
     # Подсчет количества швов 
     if used_cuts > 1: 
         weldings += used_cuts - 1 
  
     residue = used_cuts_length - target_length  # Остаток от спаянных кусков оптоволокна 
     cuts_length -= target_length                # Изменение длины оставшихся кусков оптоволокна 
     count += 1                                  # Инкремент количества полученных кусков требуемой длины 
  
     # Положить остаток в массив кусков оптоволокна 
     if residue > 0: 
         cuts.append(residue) 
         cuts.sort() 
  
 # Результат 
 print(weldings, len(cuts))

 Отправлено: 28.01.22 23:26. Заголовок: Ошибка была в функци..

Ошибка была в функции поиска подходящего индекса. После сдвига правой границы, надо так же сдвигать и подходящий индекс.

 
         # Если необходимый кусок находится левее середины, то сдвинуть правую границу 
         if min_cut_len < cuts_list[index_mid]: 
             index_end = index_mid - 1 
             # Если подходящий кусок не находится слева от левой границы, 
             # то его необходимо сдвинуть на index_mid 
             if suitable_cut_index != index_start: 
                 suitable_cut_index = index_mid 
 

 Отправлено: 17.05.22 09:04. Заголовок: f = open('26-57...

f = open('26-57.txt')
n, M = map(int,f.readline().split())
count = 0
s = 0
a = [int(x) for x in f]
a = sorted(a, reverse=True)
while sum(a) > M:
s = a[0]
a.pop(0)
while s < M:
if s + a[0] <= M:
s += a[0]
a.pop(0)
count += 1
else:
for i in range(len(a) - 1, 0 , -1):
if s + a[i] >= M:
count += 1
s += a[i]
a.pop(i)
if s > M:
a.append(s - M)
break
print(count, len(a))