Задача 4. День борьбы
ответ23 мая отмечается Международный день спортивной борьбы.
Поскольку соревнования по спортивному программированию часто проходят в обстановке острой, напряжённой и упорной борьбы, правительство Берляндии поручило национальной федерации этого вида спорта организовывать и проводить все олимпиады по информатике в стране.
По мнению главы федерации, важнейшей характеристикой спортсмена (а теперь и программиста) является его вес. Поэтому атлетов распределяют на весовые категории, соперники в которых сравнительно равны по физическим возможностям.
Для первой олимпиады, проводимой под эгидой федерации, было принято решение разделить всех 1000 участников всего лишь на три весовые категории (лёгкую, среднюю и тяжёлую).
На церемонии открытия олимпиады все программисты одной весовой категории выходят на специальный помост для приветствия и фотографирования. Важнейшей характеристикой такого помоста является прочность — он должен выдержать вес всех поднявшихся на него атлетов. Помогите организаторам определить границы весовых категорий таким образом, чтобы наибольший суммарный вес борцов из одной весовой категории был наименьшим.
Найдите такое подходящее разбиение участников по весовым категориям, чтобы суммы весов первых A спортсменов (с наименьшим весом), следующих B спортсменов и последних C спортсменов (с наибольшим весом) из предложенного списка отличались как можно меньше. При этом спортсмены с одинаковым весом должны находиться в одной весовой категории.
Входные данные для этой задачи находятся в файле электронной таблицы в виде неубывающего списка натуральных чисел.
В качестве ответа запишите три числа A, B, C, дающие в сумме 1000. Баллы будут начисляться только за такие ответы, в которых спортсмены с одинаковым весом целиком попадают в одну весовую категорию. При этом чем меньше будет наибольший суммарный вес участников одной весовой категории, тем больше баллов получит решение.
Замечание
Пример: в соревновании принимают участие 10 спортсменов и их веса равны 10, 20, 30, 30, 40, 40, 50, 50, 60, 100.
Назначим шесть первых программистов в лёгкую весовую категорию (их суммарный вес 170), двух следующих — в среднюю (100), двух последних — в тяжёлую (160). Тогда помост должен выдерживать вес 170. Такой же результат даст ещё одно разбиение: шесть первых спортсменов назначить в лёгкую весовую категорию (170), трёх следующих — в среднюю (160), последнего — в тяжёлую (100). Если пять первых программистов назначить в лёгкую весовую категорию (130), трёх следующих — в среднюю (140), двух последних — в тяжёлую (160), то, на первый взгляд, можно достигнуть ещё более оптимальной прочности помоста — 160. Но тогда пятый и шестой участники (имеющие равный вес) окажутся в разных весовых категориях, что является нарушением спортивного принципа.
Ответом в этом примере будут числа 6, 2, 2 или 6, 3, 1.
Ответ на Задачу 4.
Рассмотрим несколько способов решения задачи.
Сначала посчитаем сумму всех чисел, например, используя формулу =SUM(A1:A1000). Эта сумма равна 74995. Значит, при оптимальном разбиении спортсменов на 3 группы, в каждой из трёх весовых категорий сумма весов должна оказаться примерно равной 25000.
Для каждой строки посчитаем сумму чисел в блоке от начала списка до этой строки (включительно). Для этого запишем в ячейку B2 формулу =SUM($A$1:A1), затем эту формулу скопируем в блок B1:B1000. Аналогично для каждой строки посчитаем сумму чисел в блоке от конца списка до этой строки (включительно). Для этого запишем в ячейку C1000 формулу =SUM($A$1000:A1000), затем эту формулу скопируем в блок C1:C1000.
Попробуем найти в столбцах B и C значение, примерно равное 25000. В ячейке C685 находим число 25676, значит 316 последних участников в списке с весами от 78 и выше составляют тяжёлую весовую категорию с суммой весов, весьма близкой к оптимальной.
В столбце B есть два значения, близкие к искомому:
- В ячейке B334 находим число 23058, значит, если первых 334 участников в списке с весами до 72 включительно объединить в лёгкую категорию, то в средней категории суммарный вес составит 74995 − 25676 − 23058 = 26261. Это наибольшее число из трёх (23058, 25676 и 26261), и пока это лучшая из найденных прочностей помоста. При этом в средней весовой категории окажется 1000 − 316 − 334 = 350 спортсменов.
- В ячейке B398 находим число 27730, значит, участников с весами до 73 включительно можно объединить в лёгкую категорию. Однако их суммарный вес (27730) хуже, чем 26261, найденный нами в разборе предыдущего случая.
Перебором других близких вариантов можно убедиться, что это лучшее решение.
Ответ: 334, 350, 316.
С учётом того, что в списке много повторяющихся весов, можно сильно облегчить себе работу (и сократить обрабатываемые данные), если понять, что все значения у спортсменов одного и того же веса можно сложить в одно число — ведь их всё равно нельзя делить на части. Создадим новый столбец с уникальными весами. Для этого скопируем столбец A в новое место (например, в столбец D) и избавимся от повторов (в MS EXCEL это можно сделать кнопкой «Удалить дубликаты» на вкладке «Данные». Останется всего 33 различных значений весов. Теперь просуммируем значения с одинаковыми весами и расположим их в соседнем столбце. Объём работы сократился с 1000 строк до 33.
