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