Отправлено: 10.04.23 22:11. Заголовок: Задача 5399 - тестирую решение, предложенное на сайте

Напомню формулировку задачи:
(№ 5399) (М. Шагитов) На склад торговой базы поступают товары в ящиках, которые имеют стандартный размер и разный вес. Ящики размещаются в контейнерах, каждый из которых вмещает два пакета с суммарным весом не более D кг. Если при этом какие-то пакеты не удалось упаковать в контейнеры парами (из-за слишком большого веса), они размещаются по одному. Гарантируется, что вес каждого ящика не превышает D. Определите наибольшее количество контейнеров, в которые можно поместить по 2 ящика, и минимально возможный суммарный вес ящиков, которые размещаются по одному в контейнере.

Обычно написанная программа тестируется на достаточно большом наборе входных данных, но в задачах ЕГЭ мы получаем только один вариант файла с исходными данными. Поэтому возникает "философский" вопрос, как решать задачу? Очевидно, что написать программу, получающую правильный результат для для одного конкретного варианта, намного проще, и подавляющее число школьников выберет этот подход. Но приводить на сайте такое решение без оговорки, что оно даёт правильный результат не во всех случаях я считаю неверным. Приведу пример файла, для которого программа, приведенная на сайте, даёт неверный результат. Замечу сразу, что в условии задачи не оговаривается четность числа ящиков.

 
 9 130 
 60 
 42 
 63 
 55 
 59 
 44 
 81 
 57 
 61 
 

После сортировки веса ящиков образуют следующую последовательность: [42, 44, 55, 57, 59, 60, 61, 63, 81]
Формируем 4 пары: 44+81=125, 55+63=118, 57+61=118, 59+60=119, остаётся ящик весом 42, что является минимальным значением. Однако программа получает другой результат: 4 59, но 59>42...

 Отправлено: 04.06.23 21:08. Заголовок: Спасибо за замечание..

Спасибо за замечание. По согласованию с автором решение изменено, теперь оно проходит и ваш тест правильно.

 with open('26-91.txt') as F: 
   N, D = map( int, F.readline().split() ) 
   data = [ int(F.readline()) for _ in range(N) ] 
  
 data.sort( reverse = True ) 
 data.append( -max(data) ) 
  
 i, count = 0, 0 
 while True: 
   j = len(data) - 1 
   while data[ i] + data[j] <= D: 
     j -= 1 
     if i == j: break 
   if data[j+1] > 0: 
     count += 1 
     # print( data[ i], data[j+1] ) 
     del data[j+1] 
     del data[ i] 
   else:  # переход к следующему по величине пакету 
     i += 1 
   if i >= len(data)-1: break 
  
 print( count, sum(data[:-1]) )