A and B (Codeforces 1278B)
Tags: Greedy, math

You are given two integers $$$a$$$ and $$$b$$$. You can perform a sequence of operations: during the first operation you choose one of these numbers and increase it by $$$1$$$; during the second operation you choose one of these numbers and increase it by $$$2$$$, and so on. You choose the number of these operations yourself.For example, if $$$a = 1$$$ and $$$b = 3$$$, you can perform the following sequence of three operations:   add $$$1$$$ to $$$a$$$, then $$$a = 2$$$ and $$$b = 3$$$;  add $$$2$$$ to $$$b$$$, then $$$a = 2$$$ and $$$b = 5$$$;  add $$$3$$$ to $$$a$$$, then $$$a = 5$$$ and $$$b = 5$$$. Calculate the minimum number of operations required to make $$$a$$$ and $$$b$$$ equal. 

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

Output: For each test case print one integer — the minimum numbers of operations required to make $$$a$$$ and $$$b$$$ equal. 

Note: First test case considered in the statement.In the second test case integers $$$a$$$ and $$$b$$$ are already equal, so you don't need to perform any operations.In the third test case you have to apply the first, the second, the third and the fourth operation to $$$b$$$ ($$$b$$$ turns into $$$20 + 1 + 2 + 3 + 4 = 30$$$).

Sample Inputs:
3
1 3
11 11
30 20

Sample Outputs:
3
0
4

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (a, b) = readInts()
    if a > b:
        (a, b) = (b, a)
    d = b - a
    (lo, hi) = (0, d)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid * (mid + 1) <= 2 * d:
            lo = mid
        else:
            hi = mid - 1
    if 2 * d == lo * (lo + 1):
        return lo
    else:
        for i in range(4):
            t = (lo + i) * (lo + i + 1) // 2 + a - b
            if t >= 0 and t % 2 == 0:
                return lo + i
for _ in range(int(input())):
    print(solve())

Solution (Python):
def readString():
    return input().split(' ')

def readInts():
    return list(map(lambda s: int(s), readString()))

def readInt():
    return int(input())

def intsToString(ints):
    return ' '.join(intsToStrings(ints))

def intsToStrings(ints):
    return list(map(lambda i: str(i), ints))
stored = [0]
stored_map = {}
stored_map[0] = 0

def find_root(c, i1, i2):
    i3 = i1 + (i2 - i1) // 2
    v = i3 * (i3 + 1) / 2
    v2 = (i3 + 2) * (i3 + 1) / 2
    if v == c:
        return i3
    if v2 == c:
        return i3 + 1
    if v < c:
        if v2 > c:
            return i3
        else:
            return find_root(c, i3, i2)
    else:
        return find_root(c, i1, i3)

def root(c):
    return find_root(c, 0, c)
for _ in range(readInt()):
    (a, b) = tuple(readInts())
    diff = abs(a - b)
    n = root(diff)
    if n == 0:
        s = 0
    else:
        s = n * (n + 1) / 2
    while s < diff:
        n += 1
        s += n
    if s == diff:
        print(n)
        continue
    while abs(diff - s) % 2 == 1:
        n += 1
        s += n
    print(n)

Solution (Python):
import math
for _ in range(int(input())):
    (a, b) = map(int, input().split())
    val = abs(a - b)
    delta = 1 ** 2 - 4 * 1 * (-val * 2)
    pos = int((-1 + math.sqrt(delta)) / (2 * 1))
    if pos * (pos + 1) / 2 < val:
        pos += 1
    else:
        print(pos)
        continue
    if (pos * (pos + 1) / 2 - val) % 2 == 0:
        print(pos)
    else:
        while (pos * (pos + 1) / 2 - val) % 2 == 1:
            pos += 1
        print(pos)