Souveniers: Difference between revisions
Jump to navigation
Jump to search
Created page with "This problem gives us a set of rules about how individual merchants can make change based on what type of payment we use. The key insights are that we visit the merchants in o..." |
No edit summary |
||
| Line 17: | Line 17: | ||
Runtime: 10^2 * 10^2 * 10^4 = 10^8 = fast enough | Runtime: 10^2 * 10^2 * 10^4 = 10^8 = fast enough | ||
[[Category: ICPC Problems]] | |||
[[Category: gcpc2015]] | |||
[[Category: Algorithm Medium]] | |||
[[Category: Implementation Medium]] | |||
[[Category: Dynamic Programming]] | |||
Latest revision as of 07:47, 25 September 2018
This problem gives us a set of rules about how individual merchants can make change based on what type of payment we use. The key insights are that we visit the merchants in order. Given that we visit them in a specific order, we have the choice to not buy goods, buy them with gold, or buy them with silver. If we evaluate this for all possible combinations of gold and silver, we can come up with an optimal solution.
DP state:
- amount of gold coins (100)
- amount of silver coins (10k)
- which merchant we're on (100)
Store:
- The max number of souvenirs bought
Evaluate:
- Don't buy anything (same number of coins, and on the next merchant with same amount of souvenir)
- Buy in gold (next merchant with appropriate number of gold and silver remaining and one more souvenir)
- buy in silver (same as buy in gold, but do the math using silver)
Iterate over any amount of silver and gold after the last merchant and see which gives the most souvenir.
Runtime: 10^2 * 10^2 * 10^4 = 10^8 = fast enough