Editorial for WC '18 Contest 4 J3 - Inventory
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Each of the size-
items requires its very own knapsack. This amounts to
knapsacks.
Each of the size-
items cannot fit into a knapsack with any other size-
items, so this amounts to another
knapsacks. However, each of those knapsacks also has space for a size-
item, so we should go ahead and dispose of
size-
items along the way.
Finally, the remaining size- items (of which there are
) should be packed into knapsacks
at a time, with one potentially non-full knapsack remaining at the end. This amounts to another
knapsacks (or, equivalently,
knapsacks).
Comments