RATIO2 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given integers X and Y.
In one move, you can choose either X or Y, and either add 1 to or subtract 1 from the chosen number.
Find the minimum number of moves to make X\geq 2Y or Y\geq 2X.

EXPLANATION:

Let’s try to make X \geq 2Y.
Rearranging this slightly, we see that we want X - 2Y \geq 0 to hold.

If this is already true, no moves are needed.
Otherwise,

  • Increasing/decreasing X changes the value of (X-2Y) by +1 or -1 respectively.
  • Increasing/decreasing Y changes the value of (X-2Y) by -2 or +2 respectively.

Since we initially have X-2Y \lt 0, and we want to make it \geq 0, clearly the best possible move is to always decrease Y (which increases the value of (X-2Y) by 2).
Since X and Y are small, you can simply simulate the process by repeatedly decreasing Y till X-2Y\geq 0 holds, and count the number of steps.

Similarly, you can find the minimum number of moves needed to make Y\geq 2X instead (by always decreasing X).
Take the minimum of both cases.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
def calc(x, y):
    ans = 0
    while x - 2*y < 0:
        ans += 1
        y -= 1
    return ans

for _ in range(int(input())):
    x, y = map(int, input().split())
    print(min(calc(x, y), calc(y, x)))