Taekwondo King
InterviewTime limit2sMemory limit128 MB
With S < T, using combo A doubles S but adds 3 to T, and combo B adds 1 to S. Find the fewest kicks that make S equal T.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, Math, Brute force
- Solved
- No attempts yet
Problem
Taegyun is in the middle of a taekwondo bout. He is behind on points, so from now on he fights seriously and tries to catch up fast.
Taegyun has two combo kicks.
- Combo A is a huge combo that gains as many points as his current score. One use turns Taegyun's score into . The risk is that the opponent also scores 3 points, so becomes .
- Combo B gains 1 point. One use turns into .
He may use the two combos any number of times in any order, and the scores are compared after each single kick. Given Taegyun's current score and the opponent's current score , write a program that finds the minimum number of combo kicks that makes and equal.
Input
The first line contains the number of test cases (). Each of the next lines contains the current scores and for one test case, separated by a space. ()
Output
For each test case, print the minimum number of combo kicks that makes and equal, one per line.