Форум » Массивы, сортировка, работа с файлами » Задача 5399 - тестирую решение, предложенное на сайте » Ответить
Задача 5399 - тестирую решение, предложенное на сайте
gutgut: Напомню формулировку задачи: (№ 5399) (М. Шагитов) На склад торговой базы поступают товары в ящиках, которые имеют стандартный размер и разный вес. Ящики размещаются в контейнерах, каждый из которых вмещает два пакета с суммарным весом не более D кг. Если при этом какие-то пакеты не удалось упаковать в контейнеры парами (из-за слишком большого веса), они размещаются по одному. Гарантируется, что вес каждого ящика не превышает D. Определите наибольшее количество контейнеров, в которые можно поместить по 2 ящика, и минимально возможный суммарный вес ящиков, которые размещаются по одному в контейнере. Обычно написанная программа тестируется на достаточно большом наборе входных данных, но в задачах ЕГЭ мы получаем только один вариант файла с исходными данными. Поэтому возникает "философский" вопрос, как решать задачу? Очевидно, что написать программу, получающую правильный результат для для одного конкретного варианта, намного проще, и подавляющее число школьников выберет этот подход. Но приводить на сайте такое решение без оговорки, что оно даёт правильный результат не во всех случаях я считаю неверным. Приведу пример файла, для которого программа, приведенная на сайте, даёт неверный результат. Замечу сразу, что в условии задачи не оговаривается четность числа ящиков. [pre2] 9 130 60 42 63 55 59 44 81 57 61 [/pre2] После сортировки веса ящиков образуют следующую последовательность: [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...
Ответов - 1
Поляков: Спасибо за замечание. По согласованию с автором решение изменено, теперь оно проходит и ваш тест правильно. [pre2] 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]) ) [/pre2]
полная версия страницы