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: Accepted

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    for a, b in ab:
        a, b = min(a, b), max(a, b)
        s = (a*b-1)**0.5
        s_int = int(s)
        if a*b-1 > 1000:
            for i in range(s_int-10, s_int+10):
                if i*i > a*b-1:
                    s_int = i - 1
                    break
        if a == b:
            ans = 2*s_int
        elif (a*b-1)//s_int == s_int:
            ans = 2*s_int-2
        else:
            ans = 2*s_int-1
        print(ans)


main()

Submission status: Accepted

Solution code:
import math
import decimal

def hantei(f,p):
    if f*f<p :
        return True
    return False


def nibun2(l,r,p):
    if r == l:
        return l
    f = (l+r+1)//2
    if hantei(f,p):
        return nibun2(f,r,p)
    else:
        return nibun2(l,f-1,p)

r=[]
q=int(input())
for _ in range(q):
    a,b=map(int,input().split())
    p=a*b
    if p ==1:res = 0
    else:
        t = nibun2(0,10**20,p)
        res = t*2-1
        if (p-1)//t ==t:res -= 1
        if a==b:res+=1
    r.append(res)

print("\n".join(map(str,r)))

Submission status: Accepted

Solution code:
import math
Q=int(input())
ab=[list(map(int,input().split())) for _ in range(Q)]

for a,b in ab:
    
    if a>b:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
        
    c = math.ceil((a*b)**0.5-1)
    
    if c*(c+1)>=a*b:
        print(2*(c-1))
    else:
        print(2*c-1)

Submission status: Accepted

Solution code:
import math
Q = int(input())
ans = []

for i in range(Q):
    a,b = map(int,input().split())
    if a>b:
        a,b = b,a
    if a == b:
        ans.append((a-1)*2)
        continue
    c = math.ceil((a*b)**0.5-1)
    
    ans.append(c*2-2)
    if c*(c+1) < a*b:
        ans[-1] +=1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import math
Q = int(input())
ans = []

for i in range(Q):
    a,b = map(int,input().split())
    if a>b:
        a,b = b,a
    if a == b:
        ans.append((a-1)*2)
        continue
    c = math.ceil((a*b)**0.5-1)
    
    ans.append(c*2-2)
    if c*(c+1) < a*b and c+1 != b:
        ans[-1] +=1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import math
Q = int(input())
ans = []

for i in range(Q):
    a,b = map(int,input().split())
    if a>b:
        a,b = b,a
    if a == b:
        ans.append((a-1)*2)
        continue
    c = math.ceil((a*b)**0.5-1)
    
    ans.append(c*2-2)
    if c*(c+1) < a*b and a != c+1 != b:
        ans[-1] +=1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import math
Q = int(input())
ans = []

for i in range(Q):
    a,b = map(int,input().split())
    if a>b:
        a,b = b,a
    if a == b:
        ans.append((a-1)*2)
        continue
    c = math.ceil((a*b)**0.5-1)
    
    ans.append(c*2-1)
    if a <= c:
        ans[-1] -= 1
    if c*(c+1) < a*b and a != c+1 != b:
        ans[-1] +=1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import math


def calc(A, B):
    A, B = max(A, B), min(A, B)
    X = A * B
    rt = int(math.sqrt(X))
    if rt**2 == X:
        rt -= 1
    ans = rt * 2
    if B <= rt:
        ans -= 1
    if rt * (rt+1) >= X:
        ans -= 1
    return ans


def main():
    Q = int(input())
    for _ in range(Q):
        A, B = map(int, input().split())
        ans = calc(A, B)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	Q = int(input())
	for i in range(Q):
		A, B = sorted(getlist())
		if A == B:
			print(2 * A - 2)
		elif B == A + 1:
			print(2 * A - 2)
		else:
			C = int(((A * B) ** 0.5) // 1)
			if A * B == C ** 2:
				C -= 1
			if C * (C + 1) >= A * B:
				print(2 * C - 2)
			else:
				print(2 * C - 1)



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import math
Q = int(input())
lst = []
for i in range(Q):
    lst.append(list(map(int, input().split())))
for i in lst:
    if i[0] == i[1]:
        print(2*i[0] - 2)
    else:
        ans = math.floor((i[0]*i[1])**0.5)
        if ans**2 == i[0]*i[1]:
          print((ans-1)*2 - 1)
        elif ans * (ans+1) >= i[0]*i[1]:
          print(ans*2 - 2)
        else:
          print(ans*2 - 1)

Submission status: Accepted

Solution code:
import sys
from math import floor
Q = int(input())
AB = [sorted(list(map(int, input().split()))) for _ in range(Q)]

for A, B in AB:
  if A == B or A+1 == B:
    print(2*A-2)
    continue
  C = floor((A*B)**(1/2))
  if C == (A*B)**(1/2):
    C -= 1
  if C*(C+1) >= A*B:
    print(2*C-2)
  elif C*C < A*B:
    print(2*C-1)

Submission status: Accepted

Solution code:
Q = int(input())

for i in range(Q):
    A, B = map(int, input().split())
    C = int((A*B) ** 0.5)
    if C*(C+1) < A*B:
        print(2*C - 1)
    elif A*B == C*C and A != B:
        print(2*C - 3)
    else: 
        print(2*C - 2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

def trisection(l,r,f,convex=True,discrete=True):
    eps=2 if(discrete) else 10**-12
    while(r-l>eps):
        d=(r-l)//3 if(discrete) else (r-l)/3
        h1=l+d; h2=r-d
        if((f(h1)>=f(h2))^convex): r=h2
        else: l=h1
    if(discrete):
        if(convex): return min([(f(l),l),(f(l+1),l+1),(f(r),r)])[1]
        else: return max([(f(l),l),(f(l+1),l+1),(f(r),r)])[1]
    else:
        if(convex): return min([(f(l),l),(f(r),r)])[1]
        else: return max([(f(l),l),(f(r),r)])[1]

def resolve():
    for _ in range(int(input())):
        a,b=map(int,input().split())
        l=0; r=a+b
        while(r-l>1):
            h=(l+r)//2
            f=lambda x:(x+(x>=a))*(h-x+1+(h-x+1>=b))
            x=trisection(1,h,f,convex=False,discrete=True)
            if(f(x)<a*b): l=h
            else: r=h
        print(l)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    for _ in range(int(input())):
        a,b=map(int,input().split())
        s=(a*b)**.5
        c=int(s)-1 if(s==int(s)) else int(s)
        if(a>b): a,b=b,a # a<=b
        if(b-a<=1):
            print(2*a-2)
        elif(c*(c+1)>=a*b):
            print(2*c-2)
        else:
            print(2*c-1)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    q = int(input())
    ab = [tuple(map(int, input().split())) for _ in range(q)]
    for a, b in ab:
        if a > b:
            a, b = b, a
            
        if a == b or a + 1 == b:
            print(2 * a - 2)
        else:
            low, high = 1, pow(10, 9) + 5
            while low < high:
                mid = (low + high) // 2
                if mid * mid < a * b:
                    low = mid + 1
                else:
                    high = mid
            if low * (low - 1) >= a * b:
                print(2 * (low - 1) - 2)
            else:
                print(2 * (low - 1) - 1)                    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline

Q = int(input())
AB = [list(map(int, input().split())) for _ in range(Q)]

for A, B in AB:
    P = A*B-1
    b = int(math.sqrt(P))
    if b <= 1:
        if P <= 1:
            print(0)
        else:
            print(1)
        continue
    K = []
    for n in [b-1, b, b+1]:
        if P//n > n:
            border = n
        K.append(min(n, P//n))
    ans = 2*border
    if P//(border+1) == border+1:
        ans += 1
    if min(A, B) <= max(K):
        ans -= 1

    print(ans)

Submission status: Accepted

Solution code:
def sq(n):
    l = 0
    r = n
    while r-l > 1:
        m = (l+r) // 2
        if m*m < n:
            l = m
        else:
            r = m
    return l

Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    r = sq(a * b)
    if a == b:
        print(2*a-2)
    elif r*(r+1) < a*b:
        print(2*r-1)
    else:
        print(2*r-2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def df(c, d):
        res = c // d
        if res * d > c: res -= 1
        return res

    q = int(input())
    L = [list(map(int, input().split())) for _ in range(q)]
    for a, b in L:
        if (a, b) == (1, 1):
            print(0)
            continue
        c = a * b - 1
        rc = int(c ** 0.5)
        rc -= 1
        while (rc + 1) ** 2 <= c:
            rc += 1
        ans = rc * 2
        if rc * (rc + 1) > c:
            ans -= 1
        ab = [a, b]
        for k in ab:
            ans -= 1
            if k > rc:
                y = df(c, k)
                if y == 0:
                    ans += 1
                else:
                    x = df(c, y)
                    if x != k or (df(c, k) == df(c, k - 1)):
                        ans += 1
        print(ans)

main()

Submission status: Accepted

Solution code:
import math

Q = int(input())
for _ in range(Q):
    A, B = map(int, input().split())
    if A > B:
        A, B = B, A
    C1 = math.floor(math.sqrt(A) * math.sqrt(B))
    if C1 ** 2 >= A*B:
        C1 -= 1
    if C1 == 0:
        print(0)
        continue
    C2 = (A*B-1) // C1
    ans = C1 * 2
    if C1 == C2:
        ans -= 1
    if C1 >= A:
        ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
t= int(input())
for i in range(t):
    k=input().split()
    a=int(k[0])
    b=int(k[1])
    c=a*b
    d=int(c**.5)
    print(2*d-1-((d*(d+1))>=c)-(c==d*d and a!=b))

Submission status: Accepted

Solution code:
N = int(input())
Q = [[int(x) for x in input().split()] for _ in range(N)]
for i in range(N):
  a,b = Q[i]
  if a==b:
    print((a-1)*2)
    continue
  c = int((a*b)**0.5)
  if a>c and b>c:
    if c*(c+1)<a*b:
      print(c*2)
    else:
      print(c*2-1)
  else:
    if c*(c+1)<a*b:
      print(c*2-1)
    else:
      if c**2==a*b:
      	print(c*2-3)
      else:
        print(c*2-2)

Submission status: Accepted

Solution code:
Q, *AB = map(int, open(0).read().split())

for a, b in zip(*[iter(AB)] * 2):
    if a == b or a + 1 == b:
        print(2 * a - 2)
    else:
        c = int((a * b) ** 0.5)
        if c * c == a * b:
            c -= 1

        if c * (c + 1) >= a * b:
            print(2 * c - 2)
        else:
            print(2 * c - 1)

Submission status: Accepted

Solution code:
Q = int(input())
AB = [[int(i) for i in input().split()] for _ in range(Q)]
for a, b in AB :
    ret = 0
    sqrt = int((a * b) ** 0.5)
    ret += sqrt - 1
    ret += (a * b - 1) // sqrt - 1
    if a == b :
        ret += 1
    print(ret)

Submission status: Accepted

Solution code:
Q = int(input())
L = []
for i in range(Q):
    L.append([int(x) for x in input().split()])
    
for i in range(Q):
    a = min(L[i])
    b = max(L[i])
    if a == b:
        ans = 2*a-2
    elif a+1 == b:
        ans = 2*a-2
    else:
        c = int((a*b)**0.5)
        if c**2 == a*b:
            c -= 1
        if c*(c+1) >= a*b:
            ans = 2*c-2
        else:
            ans = 2*c-1
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    s.sort()
    if s == ["a", "b", "c"]:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    a, b, k = LI()
    ans = []
    for i in range(a, min(a + k, b + 1)):
        ans.append(i)
    for i in range(max(b - k + 1, a + k), b + 1):
        ans.append(i)
    for i in ans:
        print(i)
    return

#C
def C():
    abc= LI()
    abc.sort()
    a,b,c = abc
    a1 = (c - a) % 2
    b1 = (c - b) % 2
    if a1 and b1:
        print((c - a) // 2 + (c - b) // 2 + 1)
        return
    if a1 or b1:
        print((c - a) // 2 + (c - b) // 2 + 2)
        return
    print((c - a) // 2 + (c - b) // 2 )

    return

# D
# 解説AC

# a <= b として一般性を失わない
# 1: a = b のとき
# (a-k)*(a+k) = a*a - k*k < a*a
# であることを考えると0<k<aのすべてをとれて、
# 1回目にa-k,2回目にa+kもしくは2回目にa-k,1回目にa+kをとっている場合
# 満たすことがわかるこれは2*a-2人である
# ここでa*a > n*k を考えるとn,kどちらかはa-1以下である
# また、a+1以上である場合、もう一方がa-1以下であることが確定するため
# 片方がa+1以上である場合の個数はもう一方がa-1以下である場合に数えている 
# よって個数の上限が2*a-2人であるためこれが解であることがわかる
# 
# 2: c*c < a*b かつ c*(c+1) >= a*b を満たすcを考えるとき
# 1回目,2回目どちらかはc以下をとる必要があるゆえに上と同様に考えれば
# (c-k)*(c+k)を考えると0<=k<=c-1を考えればよくk=0で同じ組になることから
# 2*c-1人に見えるがc-k = aとなるときは除去しなければならないため
# 2*c-2人が解になる
# 
# 3: c*c < a*b かつ c*(c+1) < a*b を満たす最大のcを考えるとき
# 2と同様に(c-k)*(c+k)を考えるのではなく(c-k)*(c+1+k)の組として
# 考えればよく0<=k<c-1を考えてよく2*c人に見えるが、c-k=aのときだけ
# 除外する必要があるので2*c-1人が解になる 
def D():
    for _ in range(II()):
        a, b = LI()
        c = math.ceil(math.sqrt(a * b)) - 1
        print(2 * a - 2 if a == b else 2 * c - 1 - (c * (c + 1) >= a * b))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
Q = int(input())
AB = [list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
    a,b = AB[i]
    C = int((a*b)**0.5)
    if C*C == a*b:
        ans = 2*(C-1)
        if min(a,b) < C:
            ans -= 1
    elif C*(C+1) >= a*b:
        ans = 2*C - 2
    else:
        ans = 2*C - 1
    
    print(ans)

Submission status: Accepted

Solution code:
def solve(ab,i):
    return (ab - 1) // i
    
q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    ans = a - 1
    
    start_a = a + 1
    num = int((a * b) ** 0.5)
    while True:
        if solve(a*b, num) == solve(a*b, num + 1):
            break
        else:
            num += 1
    ans = num - 1
    ans += (solve(a*b, num) - 1)
    if a == b:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
q=int(input())
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    n=a*b
    if a==b:
        ans[i]=2*(a-1)
    elif n==int(n**.5)**2:
        ans[i]=(int(n**.5)-1)*2-1
    elif n<=int(n**.5)*(int(n**.5)+1):
        ans[i]=(int(n**.5)-1)*2
    else:
        ans[i]=(int(n**.5)-1)*2+1
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N)]
    def num(i,j):
        r = int((i*j)**(0.5))
        if r**2 == i*j:
            if i == j:
                print((r-1)*2)
            else:
                print((r-1)*2-1)
        else:
            if r*(r+1) >= i*j:
                print((r-1)*2)
            else:
                print(r*2-1)

    for i in range(N):
        num(X[i][0],X[i][1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
a,*t=map(int,open(0).read().split())
for a,b in zip(*[iter(t)]*2):
  c=a*b
  d=int(c**.5)
  print(2*d-1-(d*(d+1)>=c)-(c==d*d and a!=b))

Submission status: Accepted

Solution code:
AB=[list(map(int,input().split())) for i in range(int(input()))]
for a,b in AB:
    if a<b:a,b=b,a
    if a==b:
        print(2*a-2)
        continue
    c=int((a*b)**0.5)
    if a*b>c**2:
        if c*(c+1)<a*b:print(c*2-1)
        else:print(c*2-2)
    elif a*b==c**2:print((c-1)*2-1)

Submission status: Accepted

Solution code:
AB=[list(map(int,input().split())) for i in range(int(input()))]

for a,b in AB:
    if a<b:a,b=b,a
    if a==b:
        print(2*a-2)
        continue
    c=int((a*b)**0.5)
    if a*b>c**2:
        if c*(c+1)<a*b:
            print(c*2-1)
        else:
            print(c*2-2)
    elif a*b==c**2:
        print((c-1)*2-1)

Submission status: Accepted

Solution code:
## ABC 093 D Worst Case
import math
Q = int(input())
ans = []
for i in range(Q):
    A,B = list(map(int,input().split()))
    C = math.floor(math.sqrt(A*B)-1e-7)
    if A <= B:
        pass
    else:
        t = A
        A = B
        B = t
#解説より、場合分け
# コンテスト成績をA<＝Bとして、A==Bなら、
    if A == B:
        ans.append(2*A-2)
# 2A-2
# A+1==Bなら
    elif (A+1) == B:
        ans.append(2*A-2)
# 2A-2
# C^2 <AB の最大のCで C(C+1) >= ABなら
# 2C-2
    elif C*(C+1) >= A*B:
        ans.append(2*C-2)
# C^2 < ABなら
# 2C-1
    else:
        ans.append(2*C-1)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import math

Q = int(input())

AB = []
for _ in range(Q) :
    a, b = map(int, input().split())
    if a > b :
        a, b = b, a
    AB.append((a, b))

for a, b in AB :
    if a == b :
        print(2 * a - 2)
        continue

    C = int(math.sqrt(a * b))
    if C * C == a * b :
        C -= 1

    if C * (C + 1) >= a * b :
        print(2 * C - 2)
    else :
        print(2 * C - 1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

q = onem()
AAAA = [sorted(l()) for i in range(q)]

for a,b in AAAA:
    x = math.sqrt(a*b)
    y = int(x)
    if x == y:
        if a == b:
            print(y*2 -2)
        else:
            print(y*2 -3)
    else:
        if y*(y+1)< a*b:
            print(y*2-1)
        else:
            print(y*2-2)

Submission status: Accepted

Solution code:
# 5,10とする
# 片方は7位以下
# (7,7) (6,8) (5,-) (4,9) (3,11) (2,12) (1,13)
# (8,6) (9,5) (10,4) (11,3) (12,2) (13,1)
# 5,12とする
# (7,8) - (1,14) except 5
# (8,7) - (14,1)

Q = int(input())
AB = [[int(x) for x in input().split()] for _ in range(Q)]

for a,b in AB:
  if a > b:
    a,b = b,a
  answer = 0
  x = int((a*b)**0.5)-2
  while (x+1)*(x+1) < a*b:
    x += 1
  y = x
  answer = 2*x-1
  if a <= x:
    answer -= 1
  if x*(x+1) < a*b:
    answer += 1
  print(answer)

Submission status: Accepted

Solution code:
import math
Q = int(input())

for _ in range(Q):
    A, B = map(int, input().split())
    score = A*B #高橋君のスコア
    if A > B:
        A, B = B, A #常にAを小さくする
    if A == B:
        print  (2 * A -2)
    elif A+1 == B:
        print (2 * A - 2)
    else:
        c = int(math.sqrt(A*B))
        if c ** 2 == A * B:
            c -= 1
        if c * (c+1) >= A * B:
            print (2 * c -2)
        else:
            print (2 * c -1)

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def f(selected_p, selected_ceil, p, ceil, score):
    if p in selected_p:
        return (None, None)
    q = ceil
    while True:
        q += 1
        if q in selected_ceil:
            continue
        if p * q >= score:
            return (p, None)
        return (p, q)


def main():
    q = intin()
    ablist = intinl(q)

    for a, b in ablist:
        score = a * b
        ceil = int(score ** 0.5)
        if ceil ** 2 == score:
            ceil -= 1

        selected_x = [a]
        selected_y = [b]
        keep_x = []
        keep_y = []
        ans = 0

        for i in range(ceil, max(0, ceil - 100), -1):
            x, y = f(selected_x, selected_y, i, ceil, score)
            if x is not None:
                if y is None:
                    keep_x.append(x)
                else:
                    selected_x.append(x)
                    selected_y.append(y)
                    ans += 1

            y, x = f(selected_y, selected_x, i, ceil, score)
            if y is not None:
                if x is None:
                    keep_y.append(y)
                else:
                    selected_x.append(x)
                    selected_y.append(y)
                    ans += 1

        ans += min(len(keep_x), len(keep_y))

        ans += 2 * max(0, ceil - 100)
        if a <= ceil - 100:
            ans -= 1
        if b <= ceil - 100:
            ans -= 1

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q = int(input())
AB = [sorted([int(_) for _ in input().split()]) for _ in range(Q)]

for a, b in AB:
    s = a * b
    r = int(s**0.5)

    def calc(x):
        if x == 0:
            return
        elif s % x:
            return s // x
        else:
            return s // x - 1

    ans = 2 * r - 1
    if a == b or calc(r) == r:
        ans -= 1
    elif calc(r) < r:
        ans -= 2
    print(ans)

Submission status: Accepted

Solution code:
import math
for A,B in[map(int,input().split())for _ in range(int(input()))]:
 R=int(math.sqrt(A*B))
 N=not R*(R+1)<A*B
 print(2*(R-N)-(not ((N and R*R<A*B) or A==B)))

Submission status: Accepted

Solution code:
import math
for A,B in [map(int,input().split())for _ in range(int(input()))]:
 rt=int(math.sqrt(A*B))
 nc=not rt*(rt+1) < A*B
 print(2*(rt-nc) - (not ((nc and rt*rt < A*B) or A==B)))

Submission status: Accepted

Solution code:
import math
for A,B in [map(int,input().split())for _ in range(int(input()))]:
    rt=int(math.sqrt(A*B))
    nc = not rt*(rt+1) < A*B
    print(2*(rt-nc) - (not ((nc and rt*rt < A*B) or A==B)))

Submission status: Accepted

Solution code:
from math import sqrt
N=int(input())
for A,B in [map(int,input().split())for _ in range(N)]:
    rt=int(sqrt(A*B))
    crossable = rt*(rt+1) < A*B
    print(2*(rt-1+crossable)-1 + ((not crossable and rt*rt < A*B) or A==B))

Submission status: Accepted

Solution code:
import math

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

Q = int(input())
A, B = zip(*[list(map(int, input().split())) for _ in range(Q)])


def solve(a, b):
    a, b = min(a, b), max(a, b)
    assert a <= b

    if a == b:
        # print('c', a, b)
        # a * b > (a-n) * (b+n) なので、
        # (a-1, b+1), (a-2, b+2), ..., (1, b*2-1) まで選ぶ。x, y 逆にしても同じなので * 2
        return (a - 1) * 2
    if a == b - 1:
        # print('d', a, b)
        # 上と同じ
        # (a-1, b+1), (a-2, b+2), ..., (1, b*2-1) まで選ぶ。x, y 逆にしても同じなので * 2
        # y == a == b-1 は選べない。(a+1)*(b-1) == a*b なので x は a 以下にする必要があるため
        return (a - 1) * 2

    # a*b より小さい最大の c^2
    # math.sqrt(a*b-1) だとだめ
    # (10**9) * (10**9) - 1 がギリギリすぎて 10**9 になっちゃう
    c = int(math.sqrt(a * b))
    if c ** 2 == a * b:
        c -= 1

    # (a-1, b+1), (a-2, b+2), ..., (1, b+a-1) を選ぶ
    ret = a - 1
    if c * (c + 1) < a * b:
        # print('a', a, b)
        # (c, c+1), (c-1, c+2), ..., (a+1, c+(c-a)+1) まで
        ret += c - a
        # (c+1, c), (c+2, c-1), ..., (c+c-1, 1)
        ret += c
    else:
        # print('b', a, b)
        # (c, c), (c-1, c+1), ..., (a+1, c+(c-a)) まで
        ret += c - a
        # (c+1, c-1), (c+2, c-2), ..., (c+c-1, 1)
        ret += c - 1
    return ret


for a, b in zip(A, B):
    print(solve(a, b))

Submission status: Accepted

Solution code:
import math

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

Q = int(input())
A, B = zip(*[list(map(int, input().split())) for _ in range(Q)])


def solve2(a, b):
    a, b = min(a, b), max(a, b)
    assert a <= b

    if a == b:
        # print('c', a, b)
        # a * b > (a-n) * (b+n) なので、
        # (a-1, b+1), (a-2, b+2), ..., (1, b*2-1) まで選ぶ。x, y 逆にしても同じなので * 2
        return (a - 1) * 2
    if a == b - 1:
        # print('d', a, b)
        # 上と同じ
        # (a-1, b+1), (a-2, b+2), ..., (1, b*2-1) まで選ぶ。x, y 逆にしても同じなので * 2
        # y == a == b-1 は選べない。(a+1)*(b-1) == a*b なので x は a 以下にする必要があるため
        return (a - 1) * 2

    # (a-1, b+1), (a-2, b+2), ..., (1, b+a-1) を選ぶ
    ret = a - 1
    c = int(math.sqrt(a * b))
    if c ** 2 == a * b:
        c -= 1
    if c * (c + 1) < a * b:
        # print('a', a, b)
        # (c, c+1), (c-1, c+2), ..., (a+1, c+(c-a)+1) まで
        ret += c - a
        # (c+1, c), (c+2, c-1), ..., (c+c-1, 1)
        ret += c
    else:
        # print('b', a, b)
        # (c, c), (c-1, c+1), ..., (a+1, c+(c-a)) まで
        ret += c - a
        # (c+1, c-1), (c+2, c-2), ..., (c+c-1, 1)
        ret += c - 1
    return ret


for a, b in zip(A, B):
    print(solve2(a, b))

Submission status: Accepted

Solution code:
import math
def main():
	Q = int(input())
	ans = [0]*Q
	for i in range(Q):
		A, B = sorted(map(int, input().split()))
		if A == B or A+1 == B:
			ans[i] = 2*A-2
			continue

		C = int(math.sqrt(A*B))
		if C*C == A*B:
			C -= 1
		if C*(C+1) >= A*B:
			ans[i] = 2*C-2
		else:
			ans[i] = 2*C-1

	for a in ans:
		print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

q = int(input())
for _ in range(q):
    a, b = sorted(map(int, input().split()))
    if a == b:
        print(2 * a - 2)
    elif a + 1 == b:
        print(2 * a - 2)
    else:
        c = math.ceil(math.sqrt(a * b)) - 1

        if c * (c + 1) >= a * b:
            print(2 * c - 2)
        else:
            print(2 * c - 1)

Submission status: Accepted

Solution code:
Q = int(input())
Ans = ""
for i in range(Q):
    A, B = map(int, input().split())
    A, B = min(A, B), max(A, B)
    if A == B or A + 1 == B: Ans += str(2 * (A - 1)) + "\n"
    else:
        limit = int(pow(A * B, 0.5))
        if limit ** 2 == A * B: limit -= 1
        if limit * (limit + 1) >= A * B: Ans += str(2 * (limit - 1)) + "\n"
        else:Ans += str(2 * limit - 1) + "\n"

print(Ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def calc(x):
    lim=a*b
    mx=ceil(x, 2)*(x//2+1)
    return mx<lim

Q=INT()
for _ in range(Q):
    a,b=MAP()

    # 例外処理
    if a==b:
        print(a*2-2)
        continue

    # 二分探索
    low=1
    hi=10**18
    while low+1<hi:
        mid=(hi+low)//2
        if calc(mid):
            low=mid
        else:
            hi=mid
    print(low-1)