Коробка#63

Коробка (Editorial)

М'ячі задані у порядку зростання ваги, і це ключ до розв'язку.

Якщо ми хочемо покласти рівно м'ячів, то найвигідніше взяти найлегших, тобто перші у заданому порядку — будь-який інший набір такого ж розміру важитиме не менше. Отже, оптимальна відповідь завжди має вигляд префікса.

Тому достатньо йти по м'ячах зліва направо, накопичуючи суму ваг, і рахувати, скільки з них встигли поміститися до того, як сума перевищила . Як тільки додавання чергового м'яча робить суму більшою за , зупиняємось.

Оскільки м'ячів лише п'ять, складність тут неістотна. Головне — не забути, що коробка витримує рівно кілограмів включно, тому умова зупинки саме «сума », а не «сума ».