# Recycling Pens

Posted: 28 Dec, 2020

Difficulty: Easy

#### 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.
```

##### Note:

```
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**.

Approach 2

- Let’s say we want to know whether we can get
**X**usable pens or not. The key observation here is that if we can get**X + 1**usable pens then we can also get**X**usable pens and if we cannot get**X - 1**usable pens then we cannot get**X**usable pens. - Using the above observations we can do binary search on the range of
**L = 0**to**R = N**. - We will use similar steps in approach 1 to find whether for
**X = ( L + R ) / 2**we can get that many usable pens or not.- If we can get we will shift the range to the right that is
**L = X**. - Else we will shift the range to the left that is
**R = X**.

- If we can get we will shift the range to the right that is
- Each time we will find that our expected answer that is X is possible we will update the
**ANS**to**X**and we will return the final value of**ANS**.

SIMILAR PROBLEMS

# Numbers with product K

Posted: 29 Jun, 2021

Difficulty: Hard

# Find the N-th term

Posted: 29 Jun, 2021

Difficulty: Hard

# Make Array Elements Equal

Posted: 4 Jul, 2021

Difficulty: Moderate

# Ninja And Trains

Posted: 10 Jul, 2021

Difficulty: Hard

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate