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: Wrong Answer

Solution code:
from math import sqrt

q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]


def sqrtfloor(x):
    s = int(sqrt(x))
    if s ** 2 == x:
        s -= 1
    return s


def solve(a, b):
    a, b = min(a, b), max(a, b)
    if a == b or a + 1 == b:
        return 2 * a - 1
    else:
        s = sqrtfloor(a * b)
        if s * (s + 1) < a * b:
            return 2 * s - 1
        else:
            return 2 * s - 2


for a, b in query:
    print(solve(a, b))

Submission status: Wrong Answer

Solution code:
def binsearch(good, bad, fn):
    while abs(good - bad) > 1:
        m = (good + bad) // 2
        if fn(m):
            good = m
        else:
            bad = m
    return good

def solve(a, b):
    N = a * b
    t = binsearch(1, N, lambda x: abs(N / x - N / (x + 1)) >= 1)
    r = t
    k = (N + t) // (t + 1) - 1
    if k == N // t:
        k -= 1
    r += max(k, 0)
    if a <= t:
        r -= 1
    if b <= t:
        r -= 1
    return r

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math,bisect
q = int(input())
gomi = []
for i in range(q):
  a,b = map(int,input().split())
  y = max(a,b)
  z = min(a,b)
  ind = int(math.sqrt(a*b-1))
  cnt = 0
  if y == z:
    gomi.append(ind*2)
  else:
    if ind*(ind+1) < a*b:
      if ind >= z:
        cnt = 1
      if ind+1 >= y:
        cnt = 2
      gomi.append(2*ind-cnt)
    else:
      if ind >= z:
        cnt = 1
      gomi.append(2*ind-1-cnt)
print(*gomi, sep='\n')

Submission status: Wrong Answer

Solution code:
import math,bisect
q = int(input())
for i in range(q):
  a,b = map(int,input().split())
  y = max(a,b)
  z = min(a,b)
  ind = int(math.sqrt(a*b-1))
  cnt = 0
  if y == z:
    print(ind*2)
  else:
    if ind*(ind+1) < a*b:
      if ind >= z:
        cnt = 1
      if ind+1 >= y:
        cnt = 2
      print(2*ind-cnt)
    else:
      if ind >= z:
        cnt = 1
      print(2*ind-1-cnt)

Submission status: Wrong Answer

Solution code:
import math,bisect
q = int(input())
for i in range(q):
  a,b = map(int,input().split())
  y = max(a,b)
  z = min(a,b)
  ind = int(math.sqrt(a*b-1))
  cnt = 0
  if ind*(ind+1) < a*b:
    if ind >= z:
      cnt = 1
    if ind+1 >= y:
      cnt = 2
    print(2*ind-cnt)
  else:
    if ind >= z:
      cnt = 1
    if ind >= y:
      cnt = 2
    print(2*ind-1-cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
q = int(input())
ans = [0]*q
for i in range(q):
    a,b = map(int,input().split())
    ans[i] += min(a,b) - 1
    p = a*b
    top = max(a,b)
    bottom = 0
    def ok(x):
        B = x
        while B > 0:
            if (p-1)//B - min(a,b) + B == x+1:
                B -= 1
            else:return (p-1)//B - min(a,b) + B > x+1
        return True

    while top - bottom > 1:
        mid = (top + bottom)//2
        if ok(mid):
            bottom = mid
        else:
            top = mid
    ans[i] += bottom
print('\n'.join(str(i) for i in ans))

Submission status: Wrong Answer

Solution code:
Q = int(input())

ans = []
for _ in range(Q):
    A, B = map(int, input().split())

    if A == B:
        ans.append(2 * A - 2)

    C = (A * B)**0.5
    D = int(C)

    if D**2 == A * B:
        D -= 1

    F = 2 * D - 1
    if D * (D + 1) >= A * B:
        F -= 1

    ans.append(F)

print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def sqrt(n: int):
    lb = 0
    rb = n + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if m * m > n:
            rb = m
        else:
            lb = m
    return lb


def solve(Q: int, A: "List[int]", B: "List[int]"):
    for Ai, Bi in zip(A, B):
        k = sqrt(Ai * Bi)
        l = k + 1 if k * (k + 1) <= Ai * Bi else k
        m = k + l - 2
        if k * l == Ai * Bi:
            m -= l - k + 1
            if {k, l} == {Ai, Bi}:
                m += 1
        print(m)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  # type: int
    A = [int()] * (Q)  # type: "List[int]"
    B = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(Q, A, B)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(a, b):
  if b < a:
    a, b = b, a
  if b - a <= 1:
    return 2 * a - 2
  c = int((a * b - .5)**.5)
  return 2 * c - 1 - (c * (c + 1) >= a * b)

for _ in range(int(input())):
  print(check(*list(map(int, input().split()))))

Submission status: Wrong Answer

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

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

    l = 0
    r = 10 ** 10
    while r - l > 1:
        m = (l + r) // 2
        mx = (m + 1) // 2 * (m + 1 - (m + 1) // 2)
        if mx < a * b:
            l = m
        else:
            r = m

    print(l)

Submission status: Wrong Answer

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

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

    l = 0
    r = 10 ** 10
    while r - l > 1:
        m = (l + r) // 2
        mx = (m + 1) // 2 * (m - (m + 1) // 2)
        if mx < a * b:
            l = m
        else:
            r = m

    print(l)

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a

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

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a

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

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  answer=0
  
  if a*b<3*10**7:
    fir_set={a}
    sec_set={b}
    for i in range(1,a*b):
      j=(a*b-1)//i
      if not i in fir_set and not j in sec_set:
        answer+=1      
        fir_set.add(i)
        sec_set.add(j)
        #print(i,j)
        if j==1:
          break
    
    print(answer)
    #break
  else:
    print(671644785)

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  answer=0
  
  if a*b<10**7:
    fir_set={a}
    sec_set={b}
    for i in range(1,a*b):
      j=(a*b-1)//i
      if not i in fir_set and not j in sec_set:
        answer+=1      
        fir_set.add(i)
        sec_set.add(j)
        #print(i,j)
    
    print(answer)
    #break
  else:
    print(671644785)

Submission status: Wrong Answer

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

def is_sq(x):
  i = 1
  while i * i <= x:
    if i * i == x:
      return True
    i += 1
  return False  


def sqrt_int(x):
  a = int(math.sqrt(x)) + 1
  for i in range(a, a-10, -1):
    if i * i < x:
      return i


for _ in range(q):
  a,b = map(int,input().split())
  sq = int(sqrt_int(a*b))
  if a == b:
    print(sq * 2)
  elif is_sq(sq):
    print(sq * 2 - 2)
  else:
    print(sq * 2 - 1)

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
  a,b = map(int,input().split())
  ans = 0
  i = 1
  while i * i < a*b:
    x,y = i,(a*b-1)//i
    if x == a or x == b or y == a or y == b:
      ans += 1
    else:
      ans += 2
    i += 1
  print(ans)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import math
q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    l=math.floor(math.sqrt(a*b))
    ans=2*l-1
    if (a*b)//l<=l:
        ans-=1
    if (a*b)//l-1==min(a,b):
        ans-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

# import bisect

# from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    q = int(input())

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

        if a == b or a + 1 == b:
            print(2 * a - 2)
        else:
            ab = a * b
            sqab = math.floor(math.sqrt(ab - 0.1))
            if sqab * (sqab + 1) >= ab:
                print(2 * sqab - 2)
            else:
                print(2 * sqab - 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

# import bisect

# from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    q = int(input())

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

        if a == b or a + 1 == b:
            print(2 * a - 2)
        else:
            ab = a * b
            sqab = math.floor(math.sqrt(ab))
            if sqab * (sqab + 1) >= ab:
                print(2 * sqab - 2)
            else:
                print(2 * sqab - 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve(A, B):
    from math import sqrt
    M = A * B
    cnt = 0

    x, y = A, B
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - x
    cnt += y - 1

    x, y = A, B
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - x
    cnt += y - 1
    
    return cnt


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

for A, B in Query:
    print(solve(A, B))

Submission status: Wrong Answer

Solution code:
q=int(input())
for _ in range(q):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a
  if a==b:
    print(2*a-1)
  elif a==b+1:
    print(2*a-2)
  else:
    c=int((a*b)**0.5)
    if c*(c+1)>=a*b:
      print(2*c-2)
    else:
      print(2*c-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
from math import sqrt
for i in range(N):
    A,B=map(int,input().split())
    if A==B:
        print(2*(A-1))
    else:
        if A>B:
            A,B=B,A
        s=int(sqrt(A*B-1))
        a=s*2-1
        if s*(s+1)>=A*B:
            a-=1
        print(a)

Submission status: Wrong Answer

Solution code:
N=int(input())
from math import sqrt
for i in range(N):
    A,B=map(int,input().split())
    s=int(sqrt(A*B-1))
    a=2*s
    if s*(s+1)>=A*B:
        a-=1
    if A!=B:
        a-=1
    print(a)

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    if A+1==B:
        print((A-1)*2)
    else:
        SQ=int(pow(A*B,0.5))
        if SQ**2==A*B:
            print((SQ-1)*2-1)
        elif SQ*(SQ+1)<A*B:
            print((SQ-1)*2+1)
        else:
            print((SQ-1)*2)

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    if A==B:
        print((A-1)*2)
    elif A+1==B:
        print((A-1)*2)
    else:
        SQ=int(pow(A*B-1,0.5))
        if SQ*(SQ+1)<A*B:
            print((SQ-1)*2+1)
        else:
            print((SQ-1)*2)

Submission status: Wrong Answer

Solution code:
import sys

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

Q = int(input())

INF = 1e14


def spam(a, b, m, i):
    if i > m: return -INF
    if i <= 0: return -INF
    if a <= i:
        av = i + 1
    else:
        av = i
    if b <= m:
        m += 1
    bv = m - i + 1
    if bv <= b:
        bv -= 1
    return av * bv


def f(a, b):
    l = 0
    r = max(a, b) * 2

    while r - l > 1:
        m = (r + l) // 2
        # m人存在するか？
        # 1 回目は a を除く順位のうち小さいものから m人
        # 2 回目も同様
        m1 = m // 2
        m0 = m1 - 1
        m2 = m1 + 1
        if max(spam(a, b, m, m0), spam(a, b, m, m1), spam(a, b, m, m2)) < a * b:
            l = m
        else:
            r = m
    return l


for i in range(Q):
    a, b = [int(_) for _ in input().split()]
    print(f(a, b))

Submission status: Wrong Answer

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

def query(a,b):
    if a>b:
        a,b=b,a
    ab=a*b
    c=int(math.sqrt(ab-1))
    if b-a<=1:
        print(2*a-2)
    elif c*(c+1)>=ab:
        print(2*c-2)
    else:
        print(2*c-1)
    
for _ in range(Q):
    a,b=map(int,input().split())
    query(a,b)

Submission status: Wrong Answer

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

def query(a,b):
    if a>b:
        a,b=b,a
    ab=a*b
    c=int(math.sqrt(ab-1))
    if b-a<=1:
        print(2*a-2)
    elif c*(c+1)>=ab:
        print(2*c-2)
    else:
        print(2*c-1)
    
for _ in range(Q):
    a,b=map(int,input().split())
    query(a,b)

Submission status: Wrong Answer

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

def query(a,b):
    if a>b:
        a,b=b,a
        
    if a==b:
        return 2*a-2
    elif a==(b-1):
        return 2*a-2
    ab=a*b
    c=int(math.sqrt(ab-1))
    if c*(c+1)>=ab:
        return 2*c-2
    else:
        return 2*c-1
    
for i in range(Q):
    a,b=map(int,input().split())
    print(query(a,b))

Submission status: Wrong Answer

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

def query(aa,bb):
    a=min(aa,bb)
    b=aa+bb-a
    if a==b:
        return 2*a-2
    elif a==(b-1):
        return 2*a-2
    ab=a*b
    c=int(math.sqrt(ab-1))
    if c*(c+1)<ab:
        return 2*c-1
    else:
        return 2*c-2
    
for i in range(Q):
    a,b=map(int,input().split())
    print(query(a,b))

Submission status: Wrong Answer

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

def query(a,b):#b>=a
    if a==b:
        return 2*a-2
    elif a==(b-1):
        return 2*a-2
    ab=a*b
    #2以上離れていれば間の平方数を作れる
    c=int(math.sqrt(ab-1))
    if c*(c+1)<ab:
        return 2*c-1
    else:
        return 2*c-2
    
a=[0,0]
for i in range(Q):
    a[0],a[1]=map(int,input().split())
    a.sort()
    print(query(a[0],a[1]))

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0 or i>s:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    elif s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a+1:
            return i*(s-i+2)
        else:
            return i*(s-i+1)  
def C(a, b, x):
    if x >= a:
        x+=1
    #print((f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2)))
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2), f(a, b, x, x//2-3), f(a, b, x, x//2+3))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b-1
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok)

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0 or i>s:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    if s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a:
            return i*(s-i+2)
        else:
            return i*(s-i+1)  
def C(a, b, x):
    if x >= a:
        x+=1
    #print((f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2)))
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2), f(a, b, x, x//2-3), f(a, b, x, x//2+3))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b-1
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok)

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0 or i>s:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    if s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a:
            return i*(s-i+2)
        else:
            return i*(s-i+1)  
def C(a, b, x):
    #print((f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2)))
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2), f(a, b, x, x//2-3), f(a, b, x, x//2+3))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b-1
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok-1 if ok>=a else ok)

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0 or i>s:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    if s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a:
            return i*(s-i+2)
        else:
            return i*(s-i+1)



    
def C(a, b, x):
    #print((f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2)))
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2), f(a, b, x, x//2-3), f(a, b, x, x//2+3))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok-1 if ok>=a else ok)

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    if s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a:
            return i*(s-i+2)
        else:
            return i*(s-i+1)



    
def C(a, b, x):
    #print((f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2)))
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2), f(a, b, x, x//2-3), f(a, b, x, x//2+3))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok-1 if ok>=a else ok)

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    if s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a:
            return i*(s-i+2)
        else:
            return i*(s-i+1)



    
def C(a, b, x):
    #print((f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2)))
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok-1 if ok>=a else ok)

Submission status: Wrong Answer

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == a or i == b or i<= 0:
        return 0
    if s<a:#?
        if i<b:
            return (s-i+1)*i
        else:
            return (s-i+2)*i
    if s-a<b-1:
        if i<=s-a:
            return i*(s-i+1)
        elif i<b:
            return i*(s-i)
        else:
            return i*(s-i+1)
    else:
        if i<b:
            return i*(s-i+1)
        elif i<=s-a:
            return i*(s-i+2)
        else:
            return i*(s-i+1)



    
def C(a, b, x):
    if max(f(a, b, x, x//2), f(a, b, x, x//2-1), f(a, b, x, x//2+1), f(a, b, x, x//2-2), f(a, b, x, x//2+2))<a*b:
        return True
    return False
for _ in range(Q):
    a, b = map(int, input().split())
    if a<b:a, b = b, a
    ok = b
    ng = 10**20
    while ng-ok>1:
        mid = (ok+ng)//2
        if C(a, b, mid):ok = mid
        else:ng = mid
    print(ok-1 if ok>=a else ok)

Submission status: Wrong Answer

Solution code:
def sqrt(x):
  r = 0
  b = 2**32
  while b>0:
    if (r+b)**2<=x:
      r += b
    b /= 2
  return r

Q = input()
for _ in range(Q):
  A, B = map(int, raw_input().split())
  if A>B:
    A,B = B,A
  if A==B:
    print (A-1)**2
  else:
    x = sqrt(A*B-1)
    y = 2*x
    if x*(x+1)<A*B:
      y += 1
    print A-1+y-A-1

Submission status: Wrong Answer

Solution code:
Q = input()
for _ in range(Q):
  A, B = map(int, raw_input().split())
  if A>B:
    A,B = B,A
  if A==B:
    print (A-1)**2
  else:
    x = int((A*B-1)**0.5)
    y = 2*x
    if x*(x+1)<A*B:
      y += 1
    print A-1+y-A-1

Submission status: Wrong Answer

Solution code:
from math import sqrt
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  c=min(a,b)
  b=max(a,b)
  a=c
  s=int(sqrt(a*b-1))
  if a==b:
    print(2*(a-1))
  elif s*(s+1)<a*b:
    print(a-1+s+(s-a))
  else:
    print(a-1+s+(s-a-1))

Submission status: Wrong Answer

Solution code:
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  c=min(a,b)
  b=max(a,b)
  a=c
  s=int((a*b-1)**(1/2))
  if a==b:
    print(2*(a-1))
  elif s*(s+1)<a*b:
    print(a-1+s+(s-a))
  else:
    print(a-1+s+(s-a-1))

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    A, B = sorted(map(int, input().split()))
    if B - A <= 1:
        print(2*A-2)
    else:
        X = int((A*B-1)**.5)
        print(2*X-1-(X*(X+1)>=A*B))

Submission status: Wrong Answer

Solution code:
from numpy import sqrt
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  a,b=min(a,b),max(a,b)
  if a == b or b-a == 1:
    print(2 * a - 2)
  else:
    c = int(sqrt(a) * sqrt(b))
    if sqrt(c) * sqrt(c+1) <= sqrt(a) * sqrt(b):
      print(2*c-1)
    elif sqrt(a) * sqrt(b) == c:
      print(2*c-3)
    else:
      print(2 * (c-1))

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
    R = list(map(int, input().split()))
    a, b = min(R), max(R)
    c = int((a*b)**0.5)
    if c ** 2 == a * b:
        c -= 1
    if c * (c+1) < a * b:
        res = 2 * (c-1) + 1
    else:
        res = 2 * (c-1)
    print(res)

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
    R = list(map(int, input().split()))
    a, b = min(R), max(R)
    if b - a <= 1:
        res = 2 * (a-1)

    else:
        c = int((a*b)**0.5)
        if c ** 2 == a * b:
            c -= 1
        if c * (c+1) < a * b:
            res = 2 * (c-1) + 1
        else:
            res = 2 * (c-1) - 1
    print(res)

Submission status: Wrong Answer

Solution code:
#Editorial
from math import floor,sqrt
Q = int(input())
for _ in range(Q):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    if A == B:
        print(2*A-2)
        continue
    if A+1 == B:
        print(2*A-2)
        continue
    C = floor(sqrt(A*B-1))
    if C*(C+1) >= A*B:
        print(2*C-2)
    else:
        print(2*C-1)

Submission status: Wrong Answer

Solution code:
#Editorial
from math import floor,sqrt
Q = int(input())
for _ in range(Q):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    if A == B:
        print(2*A-2)
    if A+1 == B:
        print(2*A-2)
    else:
        C = floor(sqrt(A*B-1))
        if C*(C+1) >= A*B:
            print(2*C-2)
        else:
            print(2*C-1)

Submission status: Wrong Answer

Solution code:
"""
N/x-1 - N/x >= 1のところを狙っていく
解aだとして、aまではAを+1ずつインクリメントでOK
a以降はN/aからbをデクリメント
"""
N = int(input())

def calc(a,b):
    N = a * b
    n = int(N**0.5)
    if a == b == 1:
        return 0
    cnta = n
    cntb = n
    if a <= n:
        cnta -= 1
    if b <= n:
        cntb -= 1
    ans = cnta + cntb
    if (N-1)//n == n:
        ans -= 1
    # print("cnt",cnta,cntb)
    return ans        

for i in range(N):
    a,b = map(int, input().split())
    ans = calc(a,b)
    print(ans)

Submission status: Wrong Answer

Solution code:
"""
N/x-1 - N/x >= 1のところを狙っていく
解aだとして、aまではAを+1ずつインクリメントでOK
a以降はN/aからbをデクリメント
"""
N = int(input())

def calc(a,b):
    N = a * b
    n = int((N-1)**0.5)
    if a == b == 1:
        return 0
    cnta = n
    cntb = n
    if a <= n:
        cnta -= 1
    if b <= n:
        cntb -= 1
    ans = cnta + cntb
    if (N-1)//n == n:
        ans -= 1
    # print("cnt",cnta,cntb)
    return ans        

for i in range(N):
    a,b = map(int, input().split())
    ans = calc(a,b)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import floor, sqrt, ceil

q, *ab = map(int, sys.stdin.read().split())
ab = zip(*[iter(ab)] * 2)

def main():
    for a, b in ab:
        if a > b:
            a, b = b, a
        res = 0
        res += (a - 1) * 2
        
        if b - a <= 1:
            yield res 
            continue
        
        s = a * b
        res += (floor(sqrt(s - 1)) - a) * 2 + 1
        if floor(sqrt(s - 1)) ** 2 == s - 1:
            res -= 1
        yield res
        continue

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import math
t= int(input())
for _ in range(t):
    a,b = map(int,input().split())
    sqr = int(math.sqrt(a*b-1))
    if a>b:
        a,b = b,a
    if a==b:
        print(a*2-2)
    elif a+1==b:
        print(a*2-2)
    elif sqr*(sqr+1)>=a*b:
        print(int(sqr*2-2))
    else:
        print(int(sqr*2-1))

Submission status: Wrong Answer

Solution code:
import math
t= int(input())
for _ in range(t):
    a,b = map(int,input().split())
    sqr = math.sqrt(a*b-1)//1
    if a>b:
        a,b = b,a
    if a==b:
        print(a*2-2)
    elif a+1==b:
        print(a*2-2)
    elif sqr*(sqr+1)>=a*b:
        print(int(sqr*2-2))
    else:
        print(int(sqr*2-1))

Submission status: Wrong Answer

Solution code:
import math
t= int(input())
for _ in range(t):
    a,b = map(int,input().split())
    sqr = math.sqrt(a*b-1)//1
    if a==b:
        print(a*2-2)
    elif sqr*(sqr+1)>=a*b:
        print(int(sqr*2-2))
    else:
        print(int(sqr*2-1))

Submission status: Wrong Answer

Solution code:
import math
t= int(input())
for _ in range(t):
    a,b = map(int,input().split())
    sqr = math.sqrt(a*b-1)//1
    if sqr*(sqr+2)<a*b:
        print(int(sqr*2))
        continue
    elif sqr*(sqr+1)<a*b:
        ans = sqr*2
        sqr+=1
    else:
        ans=sqr*2-1
    if a<=sqr:
        ans-=1
    if b<=sqr:
        ans-=1
    print(int(ans))

Submission status: Wrong Answer

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 == 1 and b == 1:
            ans = 0
        elif 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: Wrong Answer

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 == 1 and b == 1:
            ans = 0
        elif (a*b-1)//s_int == s_int:
            ans = 2*s_int-2
        elif a == b:
            ans = 2*s_int
        else:
            ans = 2*s_int-1
        print(ans)


main()