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 S5=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 S5>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 S5=0. 2. Use some amount of ten-coins and 1 five-coin. This is equivalent to the case when S5=0 once we subtract 5 from the B. 3. Use all ten-coins and some amount of five-coins. We subtract 10S10 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(BlogB).