Problem:


Score : 700 points

Problem Statement

10^{10^{10}} participants, including Takahashi, competed in two programming contests.
In each contest, all participants had distinct ranks from first through 10^{10^{10}}-th.

The score of a participant is the product of his/her ranks in the two contests.

Process the following Q queries:

In the i-th query, you are given two positive integers A_i and B_i. Assuming that Takahashi was ranked A_i-th in the first contest and B_i-th in the second contest, find the maximum possible number of participants whose scores are smaller than Takahashi's.

Constraints

1 \leq Q \leq 100

1\leq A_i,B_i\leq 10^9(1\leq i\leq Q)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
A_1 B_1
:
A_Q B_Q

Output

For each query, print the maximum possible number of participants whose scores are smaller than Takahashi's.

Sample Input 1

8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323

Sample Output 1

1
12
4
11
14
57
31
671644785

Let us denote a participant who was ranked x-th in the first contest and y-th in the second contest as (x,y).

In the first query, (2,1) is a possible candidate of a participant whose score is smaller than Takahashi's. There are never two or more participants whose scores are smaller than Takahashi's, so we should print 1.



Sample input:
8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323


Sample output:
1
12
4
11
14
57
31
671644785

Submission status: Runtime Error

Solution code:
import math

text = input()

q = int(text)

array = []

for i in range(q):
    text = input()
    a = int(text.split(' ')[0])
    b = int(text.split(' ')[1])
    # array.append([a, b])

    m = a * b
    x, y = sorted([a, b])

    r = int(math.sqrt(m-1))
    cnt = r * 2

    if x <= r:
        cnt-=1

    if r * (r + 1) >= m:
        cnt-=1
    elif int((m-1) / r) == r:
        cnt -= 1

    print(cnt)

# for i in range(q):
#     a, b = array[i]
#     m = a * b
#     x, y = sorted([a, b])
#
#     r = int(math.sqrt(m-1))
#     cnt = r * 2
#
#     if x <= r:
#         cnt-=1
#
#     if r * (r + 1) >= m:
#         cnt-=1
#
#     print(cnt)

Submission status: Runtime Error

Solution code:
Q = int(input())
for i in range(Q):
    a,b = (map(int, input().split()))
    if(a == b or a+1 == b):
        print(2*a -2)
    else:
        c = int(sqrt(a*b))
        if(c*(c+1) > a*b):
            print(2*c-2)
        else:
            print(2*c-1)

Submission status: Runtime Error

Solution code:

  q = x[0]*x[1]
  buf = math.sqrt(q)
  buf = int(buf)
  if buf*buf == x[0]*x[1]:
    buf -= 1

  ans = buf * 2 - 2
  if buf*(buf+1) < x[0]*x[1]:
    ans += 1

  print ans

Submission status: Runtime Error

Solution code:
import math

text = input()

q = int(text)

array = []

for i in range(q):
    text = input()
    a = int(text.split(' ')[0])
    b = int(text.split(' ')[1])
    array.append([a, b])

for i in range(q):
    a, b = array[i]
    m = a * b
    x, y = sorted([a, b])

    r = int(math.sqrt(m-1))
    cnt = r * 2
    if x <= r:
        cnt-=1
    if int(m / r) == r:
        cnt-=1

    print(cnt)

Submission status: Runtime Error

Solution code:
# score = 4

# 1*4 <=X(takahashi)
# 2*1

# score = 50

# 1*49
# 2*24
# 3*16
# 4*12
# 5*9 <= X(takahashi)
# 6*8
# 7*7
# 8*6
# 9*5
# 10*5 <=X
# 10*4
# 11*4 <=X
# 11*3
# 12*4 <=X
# 12*3 <=X
# 12*2
# 13*1

Q = int(raw_input())

A = 0
B = 0

score = 0
num = 0
array = []

for i in range(Q):
    A, B = map(int, raw_input().split())
    score = A * B
    num = 0
    array = []
#    print 'score=', score
    for i in range(1, score):
        if i == A:
            continue
        else:
            for j in range(1, score):
                if i*(score-j) < score and not (score-j) in array and (score-j) != B:
                    array.append((score-j))
                    num += 1
#                    print i, j, (score-j)
#                    print 'add > ', num
                    break
                elif (score-j) == 1:
#                    print i,j,(score-j),'is == 1'
                    break
            if (score-j) == 1:
                break
#    print 'num =>'
    print num

Submission status: Runtime Error

Solution code:
import math
q = int(input())
a = []
b = []
for i in range(q):
  ta, tb = map(int, input().split())
  if ta < tb:
    ta, tb = tb, ta
  a.append(ta)
  b.append(tb)

for i in range(q):
  target = a[i]*b[i]-1
  x = int(math.sqrt(target))
  print(2*x - 1 - (x == (target//x)) + (a[i] == b[i]))

Submission status: Runtime Error

Solution code:
def syori(a,b):
    Maxnum = a*b;
    Sqrtnum = math.sqrt(Maxnum);
    ans = Sqrtnum*2;
    fgA=0;
    fgB=0;
    if ans > a:
        fgA = 1;
    elif ans > b:
        fgB = 1;
        
    if fgA == 1:
        ans-=1;
    if fgB == 1:
        ans-=1;
    print(ans);


data = [];
Q = int(input());
for lop in range(Q): 
    Data = input().split(" ");
    data.append( Data);
for lop in range(Q): 
    syori( int( data[lop][0]) ,int(data[lop][1]))

Submission status: Runtime Error

Solution code:
Q = int(input())

ans = []

for i in range(Q):
    ans.append(0)
    data = list(map(int,input().split()))
    score = data[0]*data[1]
    
    cont1 = list(range(1,score+1))
    cont2 = list(range(1,score+1))
    
    j = 1
    
    
    cont1.pop(cont1.index(data[0]))
    cont2.pop(cont2.index(data[1]))
    
    while True:
        a1 = []
        a2 = []
        for x in cont1:
            if (score - j)%x == 0:
                if (score-j)//x in cont2: 
                    a1.append(x)
                    a2.append((score-j)//x)
                    ans[i] += 1
                
        for num1, num2 in zip(a1, a2):
            cont1.pop(cont1.index(num1))
            cont2.pop(cont2.index(num2))
            
        #print(cont1,cont2)
            
        if cont1[0] * cont2[0] >= score:
            break
            
        j+= 1

#for i in ans:
    print(ans[i])

Submission status: Runtime Error

Solution code:
Q = int(input())

ans = []

for i in range(Q):
    ans.append(0)
    data = list(map(int,input().split()))
    score = data[0]*data[1]
    
    cont1 = list(range(1,score+1))
    cont2 = list(range(1,score+1))
    
    j = 1
    
    
    cont1.pop(cont1.index(data[0]))
    cont2.pop(cont2.index(data[1]))
    
    while True:
        a1 = []
        a2 = []
        for x in cont1:
            if (score - j)%x == 0:
                if (score-j)//x in cont2: 
                    a1.append(x)
                    a2.append((score-j)//x)
                    ans[i] += 1
                
        for num1, num2 in zip(a1, a2):
            cont1.pop(cont1.index(num1))
            cont2.pop(cont2.index(num2))
            
        #print(cont1,cont2)
            
        if cont1[0] * cont2[0] >= score:
            break
            
        j+= 1

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from math import floor

query_list = []
K = int(input())

for i in range(K):
    a = map(int, input().split())
    product = a[0]*a[1]
    SUM = 0
    for j in range(product):
        if product/j == int(product/j):
            SUM += (product / j) - 1

        else:
            SUM += floor(product / j)
    print(SUM)

Submission status: Runtime Error

Solution code:
from math import floor

query_list = []
K = int(input())

for i in range(K):
    a = map(int, input().split())
    product = a[0]*a[1]

    for j in range(product):
        if product/j == int(product/j):
            SUM += (product / j) - 1

        else:
            SUM += floor(product / j)
    print(SUM)

Submission status: Runtime Error

Solution code:
def syori(a,b):
    Maxnum = a*b;
    Sqrtnum = math.sqrt(Maxnum);
    ans = Sqrtnum*2;
    fgA=0;
    fgB=0;
    if ans > a:
        fgA = 1;
    elif ans > b:
        fgB = 1;
        
    if fgA == 1:
        ans-=1;
    if fgB == 1:
        ans-=1;
    print(ans);


A = [];
B = [];
Q = int(input());
for lop in range(Q): 
    dataA,dataB = input().split(" ");
    A.append(int(dataA));
    B.append(int(dataB));
    syori(int(dataA),int(dataB));

Submission status: Runtime Error

Solution code:
Q = int(input())

while Q:
    Q -= 1
    from math import sqrt
    A, B = map(int, input().split())
    M = max(A, B)
    for i in range(min(A, B), max(A, B)):
        if i ** 2 >= A * B:
            break
        else:
            last = i
    ans = 2 * last
    if last >= min(A, B):
        ans -= 1
    if last * (last + 1) >= A * B:
        ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
#-*- coding:utf-8 -*-

if __name__ == "__main__":
    Q = int(input())
    for i in range(Q):
        A, B = list(map(int, input().split()))
        x = list(range(1, A*B+1))  # 1回目の順位(使われてないもの)
        y = list(range(1, A*B+1))  # 2回目の順位（使われてないもの）
        x.remove(A)
        y.remove(B)
        ans = 0
        for n in range(A*B-1, 1, -1):
            # xとyを使ってnを作れるか？
            can_make = False
            for i in range(len(x)):
                if n%x[i] == 0:
                    syou = int(n / x[i])
                    if syou in y:
                        # OK. 作れる
                        ans += 1
                        can_make = True
                        remove_x = x[i]
                        remove_y = syou
                        break
            if can_make:
                x.remove(remove_x)
                y.remove(remove_y)
        print(ans)

Submission status: Runtime Error

Solution code:
def compute(n1, n2):
    threshold = n1*n2-1
    count = 0
    if n1 == 1:
        index1 = 2
    else:
        index1 = 1
    index2 = threshold
    list1, list2 = [], []
    while index1 < index2:
        index2 = int(threshold/index1)
        while index2 in list2 or index2 == n2:
            index2 -= 1
        count+=1
        index1 += 1
        if index1 == n1:
            index1+=1
            
    while not (index2 == 1 or (n2 == 1 and index2==2)):
        index1 = int(threshold)/index2
        while index1 in list1 or index1 == n1:
            index1 += 1
        count+=1
        index2 -=1
        if index2 == n2:
            index2 -=1
    print(count)
    return

N = int(input().strip())
grid = []
for i in range(N):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)

for i in grid:
    compute(i[0],i[1])

Submission status: Runtime Error

Solution code:
import math
Q = int(input())
for i in range(Q):
    a, b = map(int, input().split()).sort()
    score = a * b
    root_score = math.sqrt(score)
    if root_score == int(root_score):
        print(max(int(root_score) * 2 - 1, int(root_score - 1) * 2 - 1))
    else:
        print(int(root_score) * 2 - 1)

Submission status: Runtime Error

Solution code:
import math
q=int(input())
for i in range(q):
  a,b=list(map(int,input().split())
  c=math.sqrt(a*b-1)
  if c==int(c):
    print((c-1)*2)
  else:
    print(2*c-1)