Please tell me the idea of ​​solving this problem. As an ordinary ATM problem, I am about to solve it. And what will change here?

Purchase The buyer has a set of N coins A1 ≤ A2 ≤ ... ≤ AN, each coin has exactly one piece. Find the lowest cost item that cannot be bought using only these coins.

Input format Output format Examples Input Output 5 32 1 2 4 8 16
  • Something I do not catch up with why output 32, because the sum of all the coins is 36 and this is more than 32, then it is completely possible to buy this item !? - ampawd
  • 2
    @ampawd without change, apparently - zRrr
  • @zRrr is possible without change, 16 + 8 + 5 + 2 + 1 == 32 - ampawd
  • N = 5, then the input coins: 1,2,4,8,16. Amount: 1 + 2 + 4 + 8 + 16 = 31. - user230140
  • one
    What are the restrictions on N and dignity of coins? - Harry

1 answer 1

We sort the value of the coins in ascending order. After that, we start the test from the minimum. When for the next coin its value exceeds the sum of the previous coins by more than 1, the minimum amount that cannot be paid is equal to the sum of the previous coins + 1.

To simplify the software implementation (in order not to handle separately the case when there is no such coin, this is how it is in the original example) you can add a fake coin worth more than the sum of all the coins plus one to the set.

Schematically:

 input "Количество монет=";n dim coins(0 to n) sum=0 for i = 0 to n-1 input coins(i) sum=sum+coins(i) next i coins(n)=sum+2 coins=sort(coins, asc) sum=0 for i = 0 to n if coins(i) > sum+1 then print sum+1 exit program else sum=sum+coins(i) end if next i
  • Ps. The decision does not depend on whether there are duplicates of the merits of the coins or not. Simply, if there is - it is necessary to introduce them one by one, several times the same dignity. - Akina