Add and Divide (Codeforces 1485A)
Tags: Greedy, number theory

You have two positive integers $$$a$$$ and $$$b$$$.You can perform two kinds of operations:  $$$a = \lfloor \frac{a}{b} \rfloor$$$ (replace $$$a$$$ with the integer part of the division between $$$a$$$ and $$$b$$$)  $$$b=b+1$$$ (increase $$$b$$$ by $$$1$$$) Find the minimum number of operations required to make $$$a=0$$$.

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

Output: For each test case, print a single integer: the minimum number of operations required to make $$$a=0$$$.

Note: In the first test case, one of the optimal solutions is:  Divide $$$a$$$ by $$$b$$$. After this operation $$$a = 4$$$ and $$$b = 2$$$.  Divide $$$a$$$ by $$$b$$$. After this operation $$$a = 2$$$ and $$$b = 2$$$.  Increase $$$b$$$. After this operation $$$a = 2$$$ and $$$b = 3$$$.  Divide $$$a$$$ by $$$b$$$. After this operation $$$a = 0$$$ and $$$b = 3$$$. 

Sample Inputs:
6
9 2
1337 1
1 1
50000000 4
991026972 997
1234 5678

Sample Outputs:
4
9
2
12
3
1

Solution (Python):
from math import inf

class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            (a, b) = map(int, input().split())
            pre = 0
            count = 0
            if a < b:
                count = 1
            elif a == b:
                count = 2
            else:
                if b == 1:
                    b += 1
                    pre += 1
                count = inf
                for j in range(10):
                    (x, y) = (a, b + j)
                    temp = pre + j
                    while x != 0:
                        x = int(x / y)
                        temp += 1
                    count = min(count, temp)
            result.append(count)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
""""""
import math
for i in range(int(input())):
    (a, b) = map(int, input().split())
    c = 0
    while True:
        if a < b:
            c += 1
            break
        if b == 1:
            b = b + 1
            c += 1
            continue
        x = math.log(a, b)
        y = math.log(a, b + 1)
        if x - y > 1:
            b = b + 1
            c += 1
        else:
            a = a // b
            c += 1
    print(c)

Solution (Python):
import math
for _ in range(int(input())):
    (x, y) = map(int, input().split())
    steps = 0
    if y == 1:
        steps += 1
        y += 1
    while x > 0:
        while math.log(x, y) - math.log(x, y + 1) > 1:
            steps += 1
            y += 1
        x //= y
        steps += 1
    print(steps)