Editorial for ICPC NAQ 2016 H - Nine Packs
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.
- Considering only hotdog packs
, let
denote the minimum number of packs you need to buy to have exactly
hotdogs, or
if impossible.
- Similarly, let
denote the corresponding value for the packs of buns
.
- If
, the answer is:
- Note that
.
- Computing
is an instance of the Knapsack problem (or a variant thereof), and can be solved in a similar manner as follows.
- Based on whether we buy the
pack of hotdogs (
) or not, we get the following recurrence:
- We also have the base cases:
- We have a similar recursion for
.
- Finally,
and
can be computed for all
in
using dynamic programming (or memoization).
Comments