Recycling Pens

Posted: 28 Dec, 2020
Difficulty: Easy


Try Problem

You have 'N' empty pens whose refills have been used up. You have 'R' rupees in your pocket. You have two choices of operations that you can perform each time.

1) Recycle 1 empty pen and get 'K' rupees as a reward.

2) Buy 1 refill for 'C' rupees and combine it with 1 empty pen to make one usable pen.

Your task is to find the maximum number of usable pens that you can get.

For example if you have 'N' = 5 , 'R' = 10 , 'K' = 2 , 'C' = 3. You can recycle one pen and get 2 rupees as a reward so you will have a total of 12 rupees. Now you can buy 4 refills and combine it with 4 pens to make it usable. So your answer is 4.

Input Format :
The first line of the input contains a single integer 'T', denoting the number of test cases. Then the 'T' test case follows.

The first and the only line of each test case consists of 4 non-negative integers 'N', 'R', 'K' and 'C', as described in the problem statement.
Output Format :
For each test case, print a single integer in a new line, denoting the maximum number of usable pens you can get.
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10^5
1 <= N <= 10^9
0 <= R <= 10^9
1 <= K <= 10^9
1 <= C <= 10^9

Time limit: 1 sec
Approach 1
  • We will iterate through all possible values of the usable pen, i.e from 0 to N and try to find out whether we can make these many usable pens or not.
  • Let’s say we currently want to find whether we can make X usable pens or not. To do so we will require X refills and buy X refills we need X*C amount of money.
  • We keep X pens and sell N - X pens. We will get (N-X)*K amount of money from selling it.
  • So total money with us would be R + (N-X)*K if it is greater than X*C we can make X usable pens otherwise not. Return the maximum possible value of X.
Try Problem