BUYING2 - Editorial

editorial
, ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad Hoc

PROBLEM

You are given N banknotes { A1, A2 ..., AN } given by a customer to buy sweets. One sweet costs X units.

For the number of sweets the customer wants to buy, all the banknotes are supposed to be used, that is, you shouldn’t be able to buy that many sweets by discarding any banknote.

What is the largest number of sweets does the customer want to buy?

QUICK EXPLANATION

Check whether the smallest value can be ignored. If it can, the answer is -1. Otherwise, the answer is the maximum number of sweets the customer can buy.

EXPLANATION

Let, S = ∑(i = 1 to N)Ai

Obviously, the customer can buy, at max V = floor(S / X) sweets.

  • It should be clear from the problem statement that you will always give the customer V sweets
    • Since, the statement asks you to return the maximum number of sweets he can buy by using all the banknotes.
  • All that remains to check is, whether you must use all the banknotes to buy V sweets or not.
  • I.E. you need to check if V sweets can be bought by ignoring at least one of the banknotes, which results in the customer being “Inadequate”.
    • If the customer is inadequate, you must print -1.
    • Otherwise, the answer will be V.

To buy V sweets, you must use at least V * X amount of money.

Let, R = S - (V * X) = S % X, where % is the remainder (or modulo) operation.

Lemma
If there is no banknote given whose value is less than R, then the customer is adequate.
Also, if there is a banknote whose value is less than R, then the customer is inadequate.

Proof
Let us say you could ignore a banknote b.

That means,
floor((S - b) / X) = V
floor((S - b) / X) = (S - R) / X
((S - b) / X) - (((S - b) % X) / X) = (S - R) / X

R - b = (S - b) % X

Now, if b > R then the above expression is absurd; since R - b is negative and (S - b) % X is positive.

However, if b <= R then above expression is always true.

Thus, the necessary and sufficient condition for the customer to be adequate is that there is no banknote whose value is less tan or equal to S % X. The code to solve the problem will look like

M = minimum(x: x = A[i], for all i = 1 to N)
S = sum(x: x = A[i], for all i = 1 to N)
R = S % X
if R < M
	print S / X
else
	print -1

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

1 Like
2 
#include 
#include 
using namespace std;
main() {
       int n,N,x,a[100],p[100];
       int i,j,c,d = -1,k=0,q;
       int sum;
       cin>>n;
       for(i=0;i>N;
                        cin>>x;
                        for(j=0;j>a[i];
                                         sum=sum+a[i];
                        }
                        q=x%sum;
                        i=0;
                        while(i!=N){
                                    if(q>=a[i])
                                    d=-1;
                                              i++;
                                  }
                        if(d != -1){
                                       d=sum/x;
                        }
                        p[k]=d;
                        k++;
       }
       for(i=0;i<n;i++){
                        cout<<p[i]<<"\n";
       }
      
}
1 Like
3

Is there a question you are asking? :stuck_out_tongue:

Code can be submitted to the problem and a link to your submission can be pasted. That I believe is the usual practice :slight_smile:

1 Like
4

can someone explain how we converted floor(S-b/X) to ((S - b) / X) - (((S - b) % X) / X)

5

@strawhatdragon

Let k=floor((s-b)/X)

Remember, dividend=divisor*quotient+remainder

SO, s-b = X*k + (s-b)%X

Now, rewrite floor((s-b)/X) = k = ((s - b) / X) - (((s - b) % X) / X)