Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Batteries

Hard
0/120
Average time to solve is 50m
profile
Contributed by
0 upvote
Asked in company
Infosys

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
Full screen
Console