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: Time Limit Exceeded

Solution code:
n=int(input())
a=[0 for i in range(n)]
b=[0 for i in range(n)]
c=[0 for i in range(n)]
for i in range(n):
    a[i],b[i]=[int(i) for i in input().split()]
    c[i]=a[i]*b[i]
#print(a,b)

def keisan(d,e,f):
    count=0
    old_value=10**20
    for j in range(int(d)):
        value=min(old_value,int((d-1)/(j+1)))

#        print(value)

        if old_value==value:
            value-=1

        if value>0:
            if e!=j+1 and f!=value:
                count+=1
                old_value=value
            elif e==j+1:
               pass
            elif f==value:
               pass
        else:
            break
    print(count)

for i in range(n):        
    keisan(c[i],a[i],b[i])

Submission status: Time Limit Exceeded

Solution code:
def dfs(v, visited):

    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False

Q = int(input())
a = []
b = []
for _ in range(Q):
    inp = input().split()
    a.append(int(inp[0]))
    b.append(int(inp[1]))


for i in range(Q):
    ma = max(a[i], b[i])
    mi = min(a[i], b[i])
    edges = [set() for _ in range(ma * mi)]
    matched = [-1] * ma * mi

    for j in range(1, ma * mi):
        if j == ma:
            continue

        max_num = ma * mi // j
        if max_num * j == ma * mi:
            max_num -= 1

        for num_set in range(1, max_num+1):
            if num_set == mi:
                continue
            edges[j].add(num_set)

    print(sum(dfs(s, set()) for s in range(ma * mi)))

Submission status: Accepted

Solution code:
Q=int(input())
import math 
for i in range(Q):
  a,b=map(int, input().split())
  if a==b:
    print(2*(a-1))
  else:
    d=math.isqrt(a*b-1)
    if d*(d+1)<a*b:
      print(2*d-1)
    else:
      print(2*d-2)

Submission status: Accepted

Solution code:
def isqrt(n):
	L = 0
	R = n
	while R-L > 2:
		M = (L+R)//2
		if M*M==n:
			return M
		elif M*M < n:
			L = M
		else:
			R = M 
	for ans in range(R,L-1,-1):
		if ans*ans <= n:
			return ans
	assert(False)
	return -1
def count(n,A,B):
	ans = 0

	limit = isqrt(n)
	# x = A + 1
	# while True:
	# 	if x*x <= n:
	# 		if n//x < B:
	# 			ans += 1
	# 		x += 1
	# 	else:
	# 		return ans + min(n//x,B-1)
	return max(0,limit-A) + min(n//(limit+1),B-1)
for _ in range(int(input())):
	A, B = map(int,input().split())
	print(count(A*B-1,A,B)+count(A*B-1,B,A))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

ans = []
it = iter(data)
for a,b in zip(it,it):
    if(a > b):
        a,b = b,a
    ab = a*b
    ok = 0
    ng = b*2
    while(ng-ok > 1):
        mid = (ok+ng)//2
        x = (mid//2) * ((mid+1)//2)
        if( ab > x):
            ok = mid
        else:
            ng = mid
    ans.append(max(0,ok-2*a) + 2*a-2)

print('\n'.join(map(str,ans)))

Submission status: Accepted

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


def solve(a, b):
    score = a*b
    l, r = 0, int(1e18)
    while r-l > 1:
        k = (l+r) // 2
        if k**2 < score:
            l = k
        else:
            r = k

    ans1 = l*2 - 1
    if a <= l:
        ans1 -= 1
    if b <= l and a != b:
        ans1 -= 1
    
    ans2 = 0
    if l*r < a*b:
        ans2 = l*2
        if a <= l:
            ans2 -= 1
        if b <= l and a+b != l+r:
            ans2 -= 1

    ans = max(ans1, ans2)
    return ans

  
def main():
    q = int(input())
    for i in range(q):
        a, b = map(int, input().split())
        ans = solve(a, b)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
for a in[*open(0)][1:]:a,b=map(int,a.split());c=int((a*b)**.5);print((a*b-(a!=b))//c+c-2)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        ref = a * b
        s = int(ref ** 0.5)
        ans = 2 * s - 1
        if s * (s + 1) >= ref:
            ans -= 1
        if s * s == ref and a != b:
            ans -= 1
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

# input
Q = int(input())
A, B = [None] * Q, [None] * Q
for i in range(Q):
    A[i], B[i] = sorted(map(int, input().split()))


def solve(a, b):
    w = a * b - 1
    left, right = 0, b - a
    while right - left > 1:
        x = (left + right) // 2
        v = w // (a + x)
        if v < a:
            right = x
        else:
            left = x

    n = left
    left, right = 0, n
    while right - left > 1:
        x = (left + right) // 2
        v = w // (a + x)
        if v < a + x:
            right = x
        else:
            left = x

    return right + (w // (a + right)) - (w // (a + n))


def main():
    for a, b in zip(A, B):
        ans = 2 * (a - 1) + solve(a, b)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

n = int(input())
for i in range(n):
    a,b= map(int, input().split( ))

    #解説参照
    #何度見ても解けない
    #どちらかは高橋君より良い
    #a<=bとする
    #a=b (1~a-1)*2
    #a<b c**2<abとする
    #c(c+1)>=ab？2c-2 / 2c-1

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

Submission status: Accepted

Solution code:
q = int(input())
for i in range(q):
  x,y = map(int,input().split())
  if x == y:
    print(2*(x-1))
    continue
  z = int((x*y)**0.5)
  if z**2 == x*y:
    z -= 1
  ans = 2*z-2
  if z*(z+1)<x*y:
    ans += 1
  print(ans)

Submission status: Accepted

Solution code:
Q = int(input())
querys = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
for A, B in querys:
    if A > B:
        A, B = B, A

    if A == B:
        ans = 2*(A-1)
    elif A+1 == B:
        ans = 2*(A-1)
    else:
        C = -(-((A*B)**0.5) // 1) - 1
        if C*(C+1) >= A*B:
            ans = 2*(C-1)
        else:
            ans = 2*C-1

    anss.append(int(ans))

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) < target:
        return max_i
    if target <= func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if max_i - min_i <= 1:
            return min_i
        if func(index) < target:
            index, min_i = (index + max_i)//2, index
            continue
        index, max_i = (index + min_i)//2, index


def f(N):
    def g(i):
#        print(i,I,J)
        if i < I or J < i:
            return i*(N-i+1)
        elif i == I:
            return 0
        elif I < J:
            return i*(N-i+2)
        else:
            return i*(N-i)
    I, J = A,N-B+1
    return max(g(N//2), g(N//2+1), g(N//2+2))

Q, = map(int, input().split())
for _ in range(Q):
    A, B = map(int, input().split())
    r = bsearch(A*B, 1, A*B, f)
    print(r-1)

Submission status: Accepted

Solution code:
def examC():
    ABC = LI(); ABC.sort()
    judge = ABC[2]*2-ABC[1]-ABC[0]
    ans = judge//2 + (judge%2)*2
    print(ans)
    return

def examD():
    def judge(A,B):
        if A==B:
            return (A-1)*2
        cur = int((A*B)**0.5)
        if cur**2==A*B:
            return (cur-1)*2 -1
        if cur*(cur+1)>=A*B:
            return cur*2 -2
        else:
            return cur*2-1
    Q = I()
    ans = []
    for _ in range(Q):
        a,b = LI()
        ans.append(judge(a,b))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examD()

Submission status: Accepted

Solution code:
def check(k, a, b):
    i = (k-a)//2
    return -(i+a)*(i-k) < a*b

q = int(input())
for i in range(q):
    a,b = map(int, input().split())
    if a == b:
        print(2*a-2)
        continue
    a,b = sorted([a,b])
    ans = a-1
    left = a
    right = 10**9

    while right-left > 1:
        mid = (right+left)//2
        if check(mid, a, b):
            left = mid
        else:
            right = mid
    ans += left-1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    a, b = map(int, input().split())

    p=int((a*b)**(1/2))

    if p*(p+1) < a*b:
        ans=int(2*p-1)
    elif p**2==a*b and not a==b:
        ans=int(2*p-3)
    else:
        ans=int(2*p-2)
    l.append(ans)

for i in range(n):
    print(l[i])

Submission status: Accepted

Solution code:
from math import sqrt

def func(a, b):
	if a == b:
		return (a - 1) * 2
	else:
		sq = int(sqrt(a * b))
		if a * b == sq ** 2:
			return (sq - 1) * 2 - 1
		elif sq * (sq + 1) >= a * b:
			return (sq - 1) * 2
		else:
			return sq * 2 - 1

q = int(input())
for _ in range(q):
	a, b = map(int, input().split())
	print(func(a, b))

Submission status: Accepted

Solution code:
from math import *

Q = int(input())
r = []
for x in range(Q):
  A = [int(i) for i in input().split(' ')]
  x = A[0] * A[1]
  s = floor(sqrt(x))
  if s*s == x:
    if (A[0] != s): r.append(2*s - 3)
    else: r.append(2*s-2)
  elif (s*(s+1) < x):
    r.append(2*s - 1)
  else: 
    r.append(2*s - 2)

for i in r:print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import math

def solve(a, b):
    a, b = min(a, b), max(a, b)
    if a == b:
        return 2 * a - 2

    c = int(math.sqrt(a * b)) + 2
    while True:
        if c * c < a * b:
            if c * (c + 1) >= a * b:
                return 2 * c - 2
            else:
                return 2 * c - 1
        else:
            c -= 1

Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    print(solve(a, b))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
Q = int(input())
for _ in range(Q):
    A, B = sorted(inpl())
    c = int(-(-(A*B)**0.5//1)-1)
    ans = A-1 + max(0, c-A) + (-((-A*B)//(c+1))-1)
    print(ans)

Submission status: Accepted

Solution code:
Q=int(input())
E=10**(-10)
from math import floor
def f(x):
  if min(abs(int(x)-x),abs(int(x)+1-x))<E:
    return int(x-1)
  else:
    return int(x)
  
for i in range(Q):
  a,b=map(int,input().split())
  n=a*b
  if f(n**(1/2))<a and f(n**(1/2))<b:
    if f(n**(1/2))*(f(n**(1/2))+1)<n:
      print(2*f(n**(1/2)))
    else:
      print(2*f(n**(1/2))-1)
  else:
    if f(n**(1/2))*(f(n**(1/2))+1)<n:
      print(2*f(n**(1/2))-1)
    else:
      print(2*f(n**(1/2))-2)

Submission status: Accepted

Solution code:
import math
n = int(input())
for i in range(n):
  ans = 0
  a,b = map(int,input().split())
  c = a*b
  d = int(math.sqrt(c))
  if d *d == c:
    d -= 1
  ans += d*2
  if d >= a:
    ans -= 1
  if d >= b:
    ans -= 1
  if (d * (d+1)) >= c:
    ans -= 1
  print(ans)

Submission status: Accepted

Solution code:
for i in range(input()):
  a,b=map(int,raw_input().split())
  c=int((a*b)**0.5)
  print(a*b-(a!=b))/c+c-2

Submission status: Accepted

Solution code:
q = int(input())
for i in range(q):
  a, b = list(map(int, input().split()))
  if a==b:
    ans = 2*a-2
  elif abs(a-b)==1:
    ans = 2*min(a, b)-2
  else:
    c = (a*b)**0.5
    if c%1==0:
      c = int(c)-1
    else:
      c = int(c)
    if c*(c+1)>=a*b:
      ans = 2*c-2
    else:
      ans = 2*c-1
  print(ans)

Submission status: Accepted

Solution code:
q = int(input())
for i in range(q):
  a, b = list(map(int, input().split()))
  if a==b:
    ans = 2*a-2
  elif abs(a-b)==1:
    ans = 2*min(a, b)-2
  else:
    c = (a*b)**0.5
    if c%1==0:
      c = int(c)-1
    else:
      c = int(c)
    if c*(c+1)>=a*b:
      ans = 2*c-2
    else:
      ans = 2*c-1
  print(ans)

Submission status: Accepted

Solution code:
from math import sqrt 
Q = int(input())
table=[]
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        table.append([B,A])
    else:
        table.append([A,B])
def f(a,b):
    if a==b:
        return 2*a-2
    if a+1==b:
        return 2*a-2
    m = int(sqrt(a*b))
    if m**2 ==a*b:
        return 2*m-3
    if m*(m+1) >= a*b:
        return 2*m -2
    return 2*m-1

ans = []
for a,b in table:
    ans.append(f(a,b))
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
from math import sqrt 
Q = int(input())
table=[]
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        table.append([B,A])
    else:
        table.append([A,B])
def f(a,b):
    if a==b:
        return 2*a-2
    if a+1==b:
        return 2*a-2
    m = int(sqrt(a*b))
    if m**2 ==a*b:
        m-=1
    if m*(m+1) >= a*b:
        return 2*m -2
    return 2*m-1

ans = []
for a,b in table:
    ans.append(f(a,b))
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
from math import sqrt

def func(a, b):
	if a == b:
		return (a - 1) * 2
	else:
		sq = int(sqrt(a * b))
		if a * b == sq ** 2:
			return (sq - 1) * 2 - 1
		elif sq * (sq + 1) > a * b:
			return (sq - 1) * 2
		elif sq * (sq + 1) == a * b:
			if abs(a - b) == 1:
				return (sq - 1) * 2
			else:
				return (sq - 1) * 2
		else:
			return sq * 2 - 1

q = int(input())
for _ in range(q):
	a, b = map(int, input().split())
	print(func(a, b))

Submission status: Accepted

Solution code:
from math import sqrt
q = int(input())
while(q):
    a, b = map(int, input().split())
    c = a * b
    d = int(sqrt(c))
    if(a == b):
        print((d-1) * 2)
    elif(d*d == c):
        print((d-1)*2 - 1)
    elif(d * (d + 1) < c):
        print(d*2 - 1)
    else:
        print((d-1) * 2)
    q -= 1

Submission status: Accepted

Solution code:
for i in range(input()):
  a,b=map(int,raw_input().split())
  t=int((a*b-1)**0.5)
  t-=(t*t>a*b-1)
  print 2*t-1-(t*t+t>a*b-1)+(a==b)

Submission status: Accepted

Solution code:
q=int(raw_input())
for i in range(q):
	a,b=map(int,raw_input().split())
	p=int((a*b-1)**0.5)
	if p*p>a*b-1:
		p=p-1
	r=p*2-1
	if p*p+p>a*b-1:
		r=r-1
	if a==b:
		r=r+1
	print r

Submission status: Accepted

Solution code:
import math
q=int(input())
for j in range(q):
	AB=[int(i) for i in input().split()]
	AB.sort()#4,11
	ab=AB[0]*AB[1] #44
	for i in range(int(math.sqrt(ab)),AB[1]+1):
		if i*i>=ab:
			x=i-1
			break
	if x==0:
		print(0)
		continue
	for i in range(int(ab/x),ab+1):
		if x*i>=ab:
			y=i-1
			break
	cnt1=2*x
	cnts=1 if x==y else 0
	cntdd=1 if x-AB[0]>=0 else 0
	cntdu=1 if AB[1]-y>=0 and (AB[1]+1)*(x-AB[1]+y)>=ab else 0 #x-i, y+i=c,b->c,b+1
	print(cnt1-cnts-cntdd-cntdu)

Submission status: Accepted

Solution code:
from math import ceil
q = int(input())
for _ in range(q):    
    a, b = sorted(map(int, input().split()))
    print(min(b-a, max((ceil((a*b)**0.5-a)-1)*2, (ceil((-(2*a-1)+(1+4*a*b)**0.5)/2)-1)*2-1, 0)) + 2*(a-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 094 d問題 WA
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
Comment    : 不等式での押さえ込みを意識すること
"""
from math import ceil, sqrt

Q = int(input())
for i in range(Q):
    A, B = sorted(map(int, input().split(" ")))
    s = A*B

    if A == B:
        print(2*A - 2)
    elif A == B + 1:
        print(2*A - 2)
    else:
        C = ceil(sqrt(s)) - 1
        if C*(C+1) >= s:
            print(2*C - 2)
        else:
            print(2*C - 1)

Submission status: Accepted

Solution code:
n = int(input())
arr = []
for i in range(n):
    arr.append([int(x) for x in input().split()])
for pair in arr:
    a = pair[0]
    b = pair[1]
    t = a*b
    s = int(t ** 0.5)
    if t < 3:
        print(0)
    elif a == b:
        if (a-1) * (b+1) < t:
            print((a-1)*2)
        else:
            print((a-1)*2-1)
    elif s*s == t:
        print((s-1)*2-1)
    elif s*(s+1) < t:
        print(s*2-1)
    else:
        print((s-1)*2)

Submission status: Accepted

Solution code:
import math

n = int(input())
for i in range(n):
  a,b = list(map(int,input().split()))
  c = a * b
  r = int(math.sqrt(c))
  if a == b:
    print((r - 1) * 2)
  elif r ** 2 == c:
    print((r - 1) * 2 - 1)
  elif r * (r + 1) < c:
    print((r * 2 - 1))
  else:
    print((r - 1) * 2)

Submission status: Accepted

Solution code:
from math import sqrt
Q = int(input())
que = []
for i in range(Q):
    que.append(tuple(map(int, input().split())))
for q in que:
    if q[0] == q[1]:
        print(2*q[0]-2)
    else:
        a = q[0]*q[1]
        p = int(sqrt(a))
        if p*p == a:
            p -= 1
        if a > p*(p+1):
            print(2*p-1)
        else:
            print(2*p-2)

Submission status: Accepted

Solution code:
import math

if __name__ == '__main__':
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        big = max(a, b)
        small = min(a, b)
        c = math.floor(math.sqrt(a * b))
        if c * c == a * b:
            c -= 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

debug_mode = True if len(sys.argv) > 1 and sys.argv[1] == "-d" else False
if debug_mode:
    import os
    infile = open(os.path.basename(__file__).replace(".py", ".in"))

    def input():
        return infile.readline()


# ==============================================================

from math import sqrt


def main():
    Q = int(input().strip())
    AB = [list(map(int, input().strip().split())) for _ in range(Q)]
    for a, b in AB:
        a, b = min((a, b)), max((a, b))
        cnt = 0
        if a == b:
            cnt = 2 * (a - 1)
        elif a + 1 == b:
            cnt = 2 * (a - 1)
        else:
            ab = a * b
            c = int(sqrt(ab)) if sqrt(ab) > int(sqrt(ab)) else int(sqrt(
                ab)) - 1
            if c * (c + 1) >= ab:
                cnt = 2 * (c - 1)
            elif c * (c + 1) < ab:
                cnt = 2 * c - 1
        print(cnt)


main()

# ==============================================================

if debug_mode:
    infile.close()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math
time = int(raw_input())

def check (a,b):
    num = a*b 
    count = 0
    r = math.sqrt(num)
    r = int(r)
    if num == r**2:
        count = r
    else:
        count = r+1
    if a == b:
        return count*2-2
    elif a*b == count**2:
        return count*2-3
    elif a*b > count*(count-1):
        return count*2-3
    else:
        return count*2-4
for i in range (time):
    a,b = list(map(int,raw_input().split()))
    print check(a,b)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# seishin.py
from math import sqrt
Q = int(input())
for i in range(Q):
    a, b = map(int, input().split())
    if not a < b:
        a, b = b, a
    if a == b or a+1 == b:
        print(2*a-2)
        continue
    c = int(sqrt(a*b))
    if c**2 == a*b:
        c -= 1
    if c*(c+1) >= a*b:
        print(2*c-2)
        continue
    print(2*c-1)

Submission status: Accepted

Solution code:
import math

if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        a, b = list(map(int, input().split()))
        prod = a*b
        rootInt = int(math.sqrt(prod))
        if a == b: print((a-1)*2)
        elif math.sqrt(prod) == rootInt:
            print((rootInt-2)*2+1)
        else:
            if rootInt*(rootInt+1) < prod:
                print((rootInt-1)*2+1)
            else:
                print((rootInt-1)*2)

Submission status: Accepted

Solution code:
import math
Q=int(input())
for roop in range(Q):
    X,Y=map(int,input().split())
    A=min([X,Y])
    B=max([X,Y])
    if A==B:
        print(2*A-2)
    elif A+1==B:
        print(2*A-2)
    else:
        C=int(math.sqrt(A*B))
        while(True):
            if C**2>=A*B:
                C-=1
            elif (C+1)**2<A*B:
                C+=1
            else:
                break
        if C*(C+1)>=A*B:
            print(2*C-2)
        else:
            print(2*C-1)

Submission status: Accepted

Solution code:
# editorial解法
from math import sqrt
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)
		continue

	mul = A * B
	C = int(sqrt(mul))
	if C * C == mul:
		C -= 1
	if (C + 1) * C < mul:
		print((2*C) - 1) #(A-1) + (2*C - A)
	else:
		print((2*C) - 2) #(A-1) + (2*C - A - 1)

Submission status: Accepted

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

for a, b in AB:
    a, b = min(a, b), max(a, b)
    C = int((a*b)**0.5)
    if a == b:
        print(2*a-2)
        continue

    if a + 1 == b:
        print(2*a-2)
        continue

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

Submission status: Accepted

Solution code:
import math

q = int(input())
for i in range(q):
    a, b = list(map(int, input().split()))

    c = int(math.sqrt(a * b))
    
    ans = 2 * (c - 1)
    
    if (a * b - 1) // c > c:
        ans += 2
    elif a * b == c * c:
        pass
    else:
        ans += 1

    if not (a == b == c):
        ans -= 1

    print(max(0, ans))

Submission status: Accepted

Solution code:
from math import sqrt

Q = int(input())

for i in range(Q):
    A,B = map(int, input().split())
    m=A*B

    C = int(sqrt(m))
    if C*C==m:
        C=C-1

    if A==B or B==A+1:
        ans = 2*A-2
    elif A==B+1:
        ans = 2*B-2
    elif C*(C+1)<m:
        ans = 2*C-1
    else:
        ans = 2*C-2
    print(ans)

Submission status: Accepted

Solution code:
q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    left=0
    right=a*b
    for i in range(100):
        mid=(left+right)//2
        if mid*mid<a*b:
            left=mid
        else:
            right=mid
    ret=left*2
    if ret==0:
        print(ret)
        continue
    if (a*b-1)//left==left:
        ret-=1
    if min(a,b)<=left:
        ret-=1
    print(ret)

Submission status: Accepted

Solution code:
from math import sqrt
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    t = a*b
    s = int(sqrt(t))
    an = 2 * s - 2
    if s*s == t:
        an -= 1
    if s*(s+1) < t:
        an += 1
    if a == b:
        an += 1
    print(an)

Submission status: Accepted

Solution code:
# D
import math
Q = int(input())
A_list = []
B_list = []
for _ in range(Q):
    A, B = map(int, input().split())
    A_list.append(min(A, B))
    B_list.append(max(A, B))
    
for i in range(Q):
    A = A_list[i]
    B = B_list[i]
    R = int(math.sqrt(A*B))
    
    
    if A >= B - 1:
        print(2*A-2)
    elif R*R == A*B:
        print(2*R-3)
    elif R*(R+1) >= A*B:
        print(2*R-2)
    else:
        print(2*R-1)

Submission status: Accepted

Solution code:
import math

def slv(A, B):
    A, B = (A, B) if A > B else (B, A)
    
    s = A * B
    c = math.floor(math.sqrt(A * B))
    
    if c * (c + 1) < s:
        return 2 * c - 1
    elif A == B:
        return 2 * c - 2
    elif c * c < s:
        return 2 * c - 2
    elif c * (c - 1) < s:
        return 2 * c - 3

Q = int(input())
for q in range(Q):
    A, B = map(int, input().split())
    print(slv(A, B))

Submission status: Accepted

Solution code:
import sys

def solve(a, b):
    ans = 0
    cur = int(a * b)

    left = 1
    right = cur + 1
    while left < right:
        mid = int((left + right)/2)
        z = int(mid/2)
        mx = z * (mid - z)
        if mx <= cur:
            ans = mid
            left = mid + 1
        else:
            right = mid

    if int(ans/2) * (ans - int(ans/2)) == cur and a != b:
        ans -= 1
    return ans

n = int(sys.stdin.readline())
for i in range(n):
    x = sys.stdin.readline()
    y = [int(z) for z in x.split()]
    print(max(int(solve(y[0], y[1]))-2, 0))

Submission status: Accepted

Solution code:

def st2(x, y):
    l = int((x * y * 4 - 1) ** 0.5)
    return l - 1 - int(x != y)


def st3(x, y):
    p, q = 1, (max(x, y) + 1) * 2
    while q - p > 1:
        m = (p + q) // 2
        if m * m < x * y * 4:
            p = m
        else:
            q = m
    l = p
    return l - 1 - int(x != y)

def query(x, y):
    print(st3(x, y))


def main():
    n = int(input())
    for _ in range(n):
        x, y = map(int, input().split())
        query(x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    q = int(input())
    for i in range(q):
        print(wc())

def wc():
    a, b = map(int, input().split())
    if a == b:
        return 2 * (a - 1)
    if b > a:
        a, b = b, a
    sqt = (a * b) ** 0.5
    area1 = math.ceil(sqt) - 1
    area2 = math.ceil(sqt) - 1 - b
    area3 = b - 1
    adj = -1 if (math.ceil(sqt) - 1) * math.ceil(sqt) >= a * b else 0
    return area1 + area2 + area3 + adj

main()

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
q=i1()
import math
y=[]
for i in range(q):
 y.append(i2())

for a,b in y:
 x=a*b
 c=int(math.sqrt(x))
 if c**2==x:
    c-=1
 z=2*c
 if c>0 and (x//c)==c:
   z-=1
 if c>0 and x%c==0 and (x//c-1)==c:
   z-=1
 if a<=c:
   z-=1
 if b<=c:
   z-=1
 print(z)

Submission status: Accepted

Solution code:
import math

Q = int(input())
Query = []
for i in range(Q):
    Query.append(tuple(map(int, input().split())))
for a, b in Query:
    sq = int(math.sqrt(a * b))
    ans = sq * 2 - 1
    if a == b:
        ans -= 1
    elif sq ** 2 == a * b:
        ans -= 2
    elif sq * (sq + 1) >= a * b:
        ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
for i in range(int(input())):
    a, b = map(int, input().split())
    if not a < b:
        a, b = b, a
    ans = (a-1)*2 + (a < b-1)
    c = int(sqrt(a*b))
    if c**2 == a*b:
        c -= 1
    if a < c:
        if (a*b) % c == 0:
            d = (a*b)//c - 1
        else:
            d = a*b//c
        ans += (c - a) * 2 - (c==d)
    print(ans)

Submission status: Accepted

Solution code:
q=int(raw_input())
for i in range(q):
	a,b=map(int,raw_input().split())
	p=int((a*b-1)**0.5)
	if p*p>a*b-1:
		p=p-1
	r=p*2-1
	if p*p+p>a*b-1:
		r=r-1
	if a==b:
		r=r+1
	print r

Submission status: Accepted

Solution code:
import math

def strictintsqrt(N):
    tmp=int(math.sqrt(N))
    while(tmp**2-N>0):
        tmp-=1
    return tmp

N=int(raw_input())
for n in range(N):
  a,b=map(int, raw_input().split())
  a,b=min(a,b),max(a,b)
  #tmp=int(math.sqrt(a*b-1))
  tmp=strictintsqrt(a*b-1)
  ans=tmp*2
  if ans!=0:
      if a<=tmp: ans-=1
      if (a*b-1)/tmp== a:
          ans-=1
      elif (a*b-1)/tmp == tmp:
          ans-=1
  print ans
  """  if a==b:    ans-=0
  else: ans-=1
  if (a*b-1)/a == a: ans-=1
  if tmp*tmp==a*b-1: ans-=1
  print max(ans,0)
  """

Submission status: Accepted

Solution code:
import math


def slv(A, B):
    A, B = (A, B) if A > B else (B, A)

    # print(, A, B)
    s = A * B
    c = math.floor(math.sqrt(A * B))
    # print(A, B, c)

    if c * (c + 1) < s:
        return 2 * c - 1
    elif A == B:
        return 2 * c - 2
    elif c * c < s:
        return 2 * c - 2
    elif c * (c - 1) < s:
        return 2 * c - 3


# 1
# 12
# 4
# 11
# 14
# 57
# 31
# 671644785


def main():

    Q = int(input())
    for q in range(Q):
        A, B = map(int, input().split())
        print(slv(A, B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getKth(x, a, k):
    if(k < a):
        return k
    return k + 1
def getRKth(x, a, k):
    if(x < a):
        return x - k + 1
    if(k < (x - a)):
        return x - k + 1
    return x - k
def NB(x, b):
    if(x < b):
        return x
    return x + 1
def f(x, a, b):
    mv = 5
    half = (x + 1) / 2
    rep = 0
    for delta in xrange(-mv, mv + 1):
        if(half + delta >= 1 and half + delta <= x):
            rep = max(rep, getKth(x, a, half + delta) * getRKth(NB(x, b), b, half + delta))
    half = b - a
    for delta in xrange(-mv, mv + 1):
        if(half + delta >= 1 and half + delta <= x):
            rep = max(rep, getKth(x, a, half + delta) * getRKth(NB(x, b), b, half + delta))
    half = NB(x, b) - b
    for delta in xrange(-mv, mv + 1):
        if(half + delta >= 1 and half + delta <= x):
            rep = max(rep, getKth(x, a, half + delta) * getRKth(NB(x, b), b, half + delta))
    return rep
q = int(raw_input())
while(q > 0):
    a, b = map(int, raw_input().split())
    if(a > b):
        a, b = b, a
    lo = 1
    hi = 10**19
    res = 0
    # print f(1, a, b)
    # print f(2, a, b)
    # print f(3, a, b)
    # print getKth(2, a, 1), getRKth(NB(2, b), b, 1)
    # print getKth(2, a, 2), getRKth(NB(2, b), b, 2)
    while(lo <= hi):
        mid = (lo + hi)/2
        if(f(mid, a, b) < a * b):
            lo = mid + 1
            res = mid
        else:
            hi = mid - 1
    print res
    q -= 1