Batteries

Hard
0/120
Average time to solve is 50m
Contributed by
0 upvote

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 )
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