All numbers are integers and non-negative. Given numbers S1, S3, S5, S10 and B > 0: there are S1 one-coin coins, S3 three-coin coins, S5 five-coin coins. and S10 ten-coin coins. How many coins are needed to pay off B soms? If this is not possible, output the number 0.
Input data format Integers S1, S3, S5, S10 < 2023 and 0 < B < 30000 separated by single spaces.
Output data format Non-negative integer.
Input data Output data
5 6 56 400 2 === 2
116 3 0 0 14 === 8
0 0 18 2000 15005 === 1501
2 0 600 1500 23 === 0
Auto comment: topic has been updated by DreamerShrimp (previous revision, new revision, compare).
Auto comment: topic has been updated by DreamerShrimp (previous revision, new revision, compare).
Auto comment: topic has been updated by DreamerShrimp (previous revision, new revision, compare).
This problem can be not solved with DP.
If $$$S_5 = 0$$$, we can iterate the number of one-coin used, and then we need to use some three-coin and ten-coin to form a given amount of money with minimum count. This can be solved with exgcd.
If $$$S_5 > 0$$$, it's easy to see it makes sense to use more than $$$1$$$ five-coin only when we used all ten-coins, or we could just replace $$$2$$$ five-coins with a ten-coin. So we do a case work: 1. Use some amount of ten-coins and no five-coin. This is equivalent to the case when $$$S_5 = 0$$$. 2. Use some amount of ten-coins and 1 five-coin. This is equivalent to the case when $$$S_5 = 0$$$ once we subtract 5 from the $$$B$$$. 3. Use all ten-coins and some amount of five-coins. We subtract $$$10S_{10}$$$ from $$$B$$$, and we need to form this amount of money with one-coins, three-coins and five-coins. Again, we iterate the number of one-coins used, and use exgcd for the rest.
Time Complexity: $$$O(B\log B)$$$.