DreamerShrimp's blog

By DreamerShrimp, 3 weeks ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DreamerShrimp (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DreamerShrimp (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DreamerShrimp (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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).