Batteries

Hard

0/120

Average time to solve is 50m

Contributed by

0 upvote

Asked in company

Problem statement

You have to go to a city at night which is 'M' miles away from you, using your torch and a portable charger. Initially, your torch has 'B' units of battery level. Your torch can't glow while charging, so you can't move forward while charging your torch's battery.

Every hour, you can choose to do either one of the following two things with your torch:

1. Charge: Your torch's battery level will increase by one unit.
2. Glow: You will cover one mile of your journey and if you had not walked in the previous hour, your torch's battery level would remain the same; otherwise, it will decrease by one unit more than it had decreased in the previous hour.

For example, if you walk for the first hour, the battery level will decrease by 0, i.e., remain the same, then again if you walk in the next hour, the battery level will decrease by 1, then in the next hour walk by 2, and so on. Then if you charge for an hour, the battery level will increase by 1, then in the next hour, if you choose to walk, the battery level will decrease by 0, and so on.

Note: The battery level should never go below 0.

You have to reach the city in the minimum possible time. If there are multiple ways in which you can reach the city in minimum time, you'll choose the way in which you can retain the maximum battery level.

For Example :

Let 'M' = 2, 'B' = 0.
We do the following moves:

"Glow", Battery level decreases by '0', we walk one mile towards the city.
"Charge", Battery level increases by '1'.
"Glow", Battery level decreases by '0', we walk one more mile towards the city.

Thus, we reached the city in '3' hours with a battery level of '1'.
Therefore the answer is '3 1'.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer 'T', which denotes the number of test cases.
Then 'T' test cases follow. For each test case:

The first line contains two integers, 'M' and 'B', denoting the initial distance from the city and the initial battery level of the torch, respectively.

Output Format :

For each test case, return the minimum time it will take to reach the city and the maximum possible remaining battery level after reaching the city in that minimum time.

Note :

You don’t need to print anything. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'M, B' <= 10^9

Time Limit: 1 sec

Sample Input 1 :

2
3 21
18 138

Sample Output 1 :

3 18
19 67

Explanation of sample input 1 :

First test case:-
We can simply do the "Glow" operation 3 times in a row to reach the city in '3' hours.
The first "Glow" changes the battery level from '21' to '21'. ( - 0 )
The second "Glow" changes the battery level from '21' to '20'. ( - 1 )
The third "Glow" changes the battery level from '20' to '18'. ( - 2 )
Thus, the answer is '3 18'.

Second test case:-
We can do 9 "Glow" operations followed by a "Charge" operation followed by another 9 "Glow" operations to reach the city in '19' hours.
Consecutively performing 9 "Glow" operations decreases the battery level by '0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36' units.
The first 9 "Glow" operations change the battery level from '138' to '102'. ( - 36 )
The "Charge" operation changes the battery level from '102' to '103'. ( + 1 )
The last 9 "Glow" operations change the battery level from '103' to '67'. ( - 36 )
Thus, the answer is '19 67'.

Sample Input 2 :

2
217 19
100 131

Sample Output 2 :

320 0
124 5

Console