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:
import math
r=[]
q=int(input())
for _ in range(q):
    a,b=map(int,input().split())
    p=a*b
    if p ==1:res = 0
    else:
        t = math.floor(math.sqrt(p-1))
        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: 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:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
        
    d=a*b-1
    c=int(d**0.5)
    if c*(c+1)>=a*b:
        print(2*(c-1))
    else:
        print(2*c-1)

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:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
    if a+1==b:
        print(2*(a-1))
        continue
        
    d=a*b-1
    c=int(d**0.5)
    if c*(c+1)>=a*b:
        print(2*(c-1))
    else:
        print(2*c-1)

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:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
    if a+1==b:
        print(2*(a-1))
        continue
        
    ans=2*(a-1)
    c=a*b-1
    d=int(c**0.5)

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

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:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
    if a+1==b:
        print(2*(a-1))
        continue
        
    ans=2*(a-1)
    c=a*b-1
    d=int(c**0.5)
    
    if c==d**2:
        ans+=2*(d-a)
    elif c<d*(d+1):
        ans+=2*(d-a)
    else:
        ans+=2*(d-a)+1
    
    print(ans)

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:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
        
    ans=2*(a-1)
    c=a*b-1
    d=int(c**0.5)
    
    if c==d**2:
        ans+=2*(d-a)
    elif c<d*(d+1):
        ans+=2*(d-a)
    else:
        ans+=2*(d-a)+1
    
    print(ans)

Submission status: Wrong Answer

Solution code:
import math


def calc(A, B):
    A, B = max(A, B), min(A, B)
    if A - B < 2:
        return B * 2 - 2
    X = A * B - 1
    rt = int(math.sqrt(X))
    ans = rt * 2 - 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: Wrong Answer

Solution code:
import math


def calc(A, B):
    A, B = max(A, B), min(A, B)
    if A == B:
        return B*2-2
    if A == B+1:
        return B*2-2
    X = A*B-1
    rt = int(math.sqrt(X))
    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: Wrong Answer

Solution code:
import math


def calc(A, B):
    A, B = max(A, B), min(A, B)
    X = A*B-1
    rt = int(math.sqrt(X))
    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: Wrong Answer

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

for A, B in AB:
  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: Wrong Answer

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
    for n in [b-1, b, b+1]:
        if P//n > n:
            border = n
    ans = 2*border
    if (border+1)**2 == P:
        border += 1
        ans += 1
    if min(A, B) <= border:
        ans -= 1
    print(ans)

Submission status: Wrong Answer

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 == 0:
        print(0)
        continue
    elif b == 1:
        print(1)
        continue
    for n in [b-1, b, b+1]:
        if P//n > n:
            border = n
    ans = 2*border
    if (border+1)**2 == P:
        border += 1
        ans += 1
    if min(A, B) <= border:
        ans -= 1
    print(ans)

Submission status: Wrong Answer

Solution code:
q=int(input())
ab=[list(map(int,input().split())) for i in range(q)]
for u in ab:
    a,b=u
    if a>b:
        a,b=b,a
    if a==b:
        print(2*(a-1))
    elif b-a==1:
        print(2*(a-1))
    else:
        ans=2*(a-1)
        c=int((b*a-1)**(1/2))
        if c*(c+1)>=b*a:
            print(ans+2*(c-a))
        else:
            print(ans+1+2*(c-a))

Submission status: Wrong Answer

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

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((A*B-1) ** (1/2))
    if C1 == 0:
        print(0)
        continue
    C2 = (A*B-1) // C1
    ans = C1 * 2
    if C1 == C2:
        ans -= 1
    if C1 >= A:
        ans -= 1
    if C1 >= B:
        ans -= 1
    print(ans)

Submission status: Wrong Answer

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((A*B-1) ** (1/2))
    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: Wrong Answer

Solution code:
import sys

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

def main():
    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)
        ans = rc * 2
        if c // rc == rc:
            ans -= 1
        ab = set([a, b])
        for k in ab:
            ans -= 1
            if k > rc:
                y = c // k
                if y == 0:
                    ans += 1
                else:
                    x = c // y
                    if x != k or (c // k == c // (k - 1)):
                        ans += 1
        print(ans)

main()

Submission status: Wrong Answer

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((A*B-1) ** (1/2))
    if C1 == 0:
        print(0)
        continue
    C2 = (A*B-1) // C1
    print((A-1) + (C2 + C1 - A-1))

Submission status: Wrong Answer

Solution code:
import sys

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

def main():
    q = int(input())
    for _ in range(q):
        a, b = map(int, input().split())
        if (a, b) == (1, 1):
            print(0)
            continue
        c = a * b - 1
        rc = int(c ** 0.5)
        ans = rc * 2
        if c // rc == rc:
            ans -= 1
        ab = set([a, b])
        for a in ab:
            ans -= 1
            if a > rc:
                y = c // a
                if y == 0:
                    ans += 1
                else:
                    x = c // y
                    if x != a or (c // a == c // (a - 1)):
                        ans += 1
        print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

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

def main():
    q = int(input())
    for _ in range(q):
        a, b = map(int, input().split())
        x = a * b - 1
        rx = int(x ** 0.5)
        ans = rx * 2 - 2
        if rx * (rx + 1) > x:
            ans -= 1
        if a > rx and x // a == x // (a + 1):
            ans += 1
        if b > rx and (x // b == x // (b + 1) or x // b == x // (b - 1)):
            ans += 1
        print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

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

def main():
    q = int(input())
    for _ in range(q):
        a, b = map(int, input().split())
        x = a * b - 1
        rx = x ** 0.5
        ans = int(rx) * 2 - 2
        if int(rx) * (int(rx) + 1) > x:
            ans -= 1
        if a > int(rx) and x // a == x // (a + 1):
            ans += 1
        if b > int(rx) and x // b == x // (b + 1):
            ans += 1
        print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

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

def main():
    q = int(input())
    for _ in range(q):
        a, b = map(int, input().split())
        x = a * b - 1
        rx = x ** 0.5
        ans = int(rx) * 2
        if min(a, b) <= int(rx): ans -= 1
        # if rx == int(rx): ans -= 1
        if int(rx) * (int(rx) + 1) > x: ans -= 1
        print(ans)

main()

Submission status: Wrong Answer

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

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)==c)-(c==d*d and a!=b))

Submission status: Wrong Answer

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)==c)-(c==d*d and a!=b))

Submission status: Wrong Answer

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)>=c)-(c==d*d and a!=b))

Submission status: Wrong Answer

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

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 = int(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: Wrong Answer

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

Submission status: Wrong Answer

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)
    elif (a + 1) == b :
        print(2 * a - 2)
    else :
        C = int(math.sqrt(a * b))
        if C * (C + 1) >= a * b :
            print(2 * C - 2)
        else :
            print(2 * C - 1)

Submission status: Wrong Answer

Solution code:
import math

Q = int(input())

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

for a, b in AB :
    if a == b :
        print(2 * a - 2)
    elif (a + 1) == b :
        print(2 * a - 2)
    else :
        C = int(math.sqrt(a * b))
        if C * (C + 1) >= a * b :
            print(2 * C - 2)
        else :
            print(2 * C - 1)

Submission status: Wrong Answer

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

for i in range(q):
    a = ab[i][0]
    b = ab[i][1]
    n = int((a * b) ** 0.5)

    if (a == 1 and b == 4) or (a == 4 and b == 1):
        print(1)
    else:
        if a * b >= n * (n + 1):
            print(n * 2 - 1)
        else:
            print(n * 2 - 2)

Submission status: Wrong Answer

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

for i in range(q):
    a = ab[i][0]
    b = ab[i][1]
    n = int((a * b) ** 0.5)

    if (a == 1 and b == 4) or (a == 4 and b == 1):
        print(1)
    else:
        if a * b > n * (n + 1):
            print(n * 2 - 1)
        else:
            print(n * 2 - 2)

Submission status: Wrong Answer

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

for i in range(q):
    a = ab[i][0]
    b = ab[i][1]
    n = int((a * b) ** 0.5)

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

Submission status: Wrong Answer

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-1))
        if c * (c+1) >= A * B:
            print (2 * c -2)
        else:
            print (2 * c -1)

Submission status: Wrong Answer

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))
        print (2 * c -1)

Submission status: Wrong Answer

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


def solve(Q: int, A: "List[int]", B: "List[int]"):
    for i in range(Q):
        tmp = int((A[i] * B[i] - 1) ** 0.5)
        #print(A[i] * B[i], tmp)
        #if tmp * tmp == A[i] * B[i] - 1:
        if tmp * (tmp + 1) >= A[i] * B[i]:
            ret = tmp * 2 - 1
        else:
            ret = tmp * 2

        if A[i] <= tmp:
            ret -= 1
        if B[i] <= tmp:
            ret -= 1
        print(ret)
        #print(A[i], B[i])
        #print(tmp)
        #print(ret)
        #print()

    return


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

Solution code:
import bisect
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
from operator import mul

import numpy as np
import re
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):
    """
    だめおそい
    :param a:
    :param b:
    :return:
    """
    target = a * b - 1
    max_x = int(math.sqrt(target))
    ret = set()

    used = set()
    # x*y が target 以下になる選び方
    for x in range(1, max_x + 1):
        if x == a:
            continue
        y = target // x
        while not (y not in used and y != b):
            y -= 1
        if y < max_x:
            break
        ret.add((x, y))
        used.add(y)
    used = set()
    for y in range(1, max_x + 1):
        if y == b:
            continue
        x = target // y
        while not (x not in used and x != a):
            x -= 1
        if x < max_x:
            break
        ret.add((x, y))
        used.add(x)
    print(ret)
    return len(ret)


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

    if 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:
        # 上と同じ
        # (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*2-1) を選ぶ
    ret = a - 1
    c = int(math.sqrt(a * b - 1))
    if c * (c + 1) < 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:
        # (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: Wrong Answer

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)
    point = A * B
    limit = int(pow(point, 0.5))
    if point >=5:
        if A != B:
            total = limit * 2 - 1
            lim_op = point // limit - (0 if point % limit > 0 else 1)
            if lim_op == limit: total -= 1
        else:
            total = (A-1) * 2
        Ans += str(total) + "\n"
    elif point <= 2: Ans += "0\n"
    else: Ans += "1\n"
print(Ans)

Submission status: Wrong Answer

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-1
    mx=(x+1)//2*(x+1-(x+1)//2)
    return mx>lim

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

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

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

Submission status: Wrong Answer

Solution code:
import math

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

def max_multi(a,b,d,c):
        length = b-a
        n = math.ceil((d-a)/2)
        if n < 0:
            n = 0
        elif n > length:
            n = length
        x = (a+n)*(d-n)
        n = math.floor((d-a)/2)
        if n < 0:
            n = 0
        elif n > length:
            n = length
        y = (a+n)*(d-n)
        return max(x,y)

def check(a, b, n):
    multi = a*b
    if n<a:
        return True
    else:
        if a<= n < b:
            #second_1 = [i for i in range(1, n+1)][::-1]
            second_1 = (n,1)
            second_2 = (0,0)
        else:
            #second_1 = [i for i in range(1, b)][::-1]
            second_1 = (b-1,1)
            #second_2 = [i for i in range(b+1, n+2)][::-1]  
            second_2 = (n+1, b+1)
        m = (second_2[0] - second_2[1])+1
        #print('m :', m)
        if second_2 == (0,0):
            a1,b1,c1,d1 = 1, a-1, second_1[0], second_1[0]-(a-2)
            a2,b2,c2,d2 = a+1, n+1, second_1[0]-(a-1), second_1[1]
            #print(a1,b1,c1,d1)
            #print(a2,b2,c2,d2)
            s = max(max_multi(a1,b1,c1,d1), max_multi(a2,b2,c2,d2))
        elif m == a-1:
            a1,b1,c1,d1 = 1, a-1, second_2[0], second_2[1]
            a2,b2,c2,d2 = a+1, n+1, second_1[0], second_1[1]
            #print(a1,b1,c1,d1)
            #print(a2,b2,c2,d2)
            #print(max_multi(a1,b1,c1,d1), max_multi(a2,b2,c2,d2))
            s = max(max_multi(a1,b1,c1,d1), max_multi(a2,b2,c2,d2))
        elif m > a-1:
            a1,b1,c1,d1 = 1, a-1, second_2[0], second_2[0]-(a-2)
            a2,b2,c2,d2 = a+1, m+1, second_2[0]-(a-1), second_2[1]
            a3,b3,c3,d3 = m+2, n+1, second_1[0], second_1[1]
            #print(a1,b1,c1,d1)
            #print(a2,b2,c2,d2)
            #print(a3,b3,c3,d3)
            s = max(max_multi(a1,b1,c1,d1), max_multi(a2,b2,c2,d2), max_multi(a3,b3,c3,d3))
        else:
            a1,b1,c1,d1 = 1,m,second_2[0], second_2[1]
            a2,b2,c2,d2 = m+1, a-1, second_1[0], second_1[0]-(a-m-2)
            a3,b3,c3,d3 = a+1, n+1, second_1[0]-(a-m-1), second_1[1]
            #print(a1,b1,c1,d1)
            #print(a2,b2,c2,d2)
            #print(a3,b3,c3,d3)
            s = max(max_multi(a1,b1,c1,d1), max_multi(a2,b2,c2,d2), max_multi(a3,b3,c3,d3))
        return True if s < multi else False

def search(a,b):
    a,b = min(a,b), max(a,b)
    low = a
    high = 10**30
    while high - low > 1:
        if check(a,b,(low+high)//2):
            low = (low+high)//2
            #print('low :', low)
        else:
            high = (low+high)//2
            #print('high :', high)
    return high if check(a,b,high) else low

for i in lst:
    print(search(i[0], i[1]))

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
a = [0] * q
b = [0] * q

for i in range(0, q):
    a[i], b[i] = [int(i) for i in input().split(" ")]
    
def sqrt_int(n):
    s = math.floor(n**(1/2)) - 1
    while s * s <= n:
        s += 1
    return s - 1

for i in range(0, q):
    mi = min(a[i], b[i])
    mx = max(a[i], b[i])
    p = mi * mx - 1
    s = sqrt_int(p)
    c = 2 * (s - 1)
    if s == 0:
        print(0)
        continue
    if mi <= s - 1:
        c -= 1
    r = p // s
    if r > s:
        if s == mi:
            c += 1
        elif s < mi:
            c += 2
    elif r == s and s != mi:
        c += 1
    print(c)

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
a = [0] * q
b = [0] * q

for i in range(0, q):
    a[i], b[i] = [int(i) for i in input().split(" ")]
    
def sqrt_int(n):
    s = math.floor(n**(1/2)) - 1
    while s * s <= n:
        s += 1
    return s - 1

for i in range(0, q):
    mi = min(a[i], b[i])
    mx = max(a[i], b[i])
    p = mi * mx - 1
    s = sqrt_int(p)
    c = 2 * (s - 1)
    if s == 0:
        print(0)
        continue
    if mi <= s - 1:
        c -= 1
    r = p // s
    if r > s:
        if s == mi:
            c += 1
        elif s > mi:
            c += 2
    elif r == s and s != mi:
        c += 1
    print(c)

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
a = [0] * q
b = [0] * q

for i in range(0, q):
    a[i], b[i] = [int(i) for i in input().split(" ")]
    
def sqrt_int(n):
    s = math.floor(n**(1/2)) - 1
    while s * s <= n:
        s += 1
    return s - 1

for i in range(0, q):
    mi = min(a[i], b[i])
    mx = max(a[i], b[i])
    p = mi * mx - 1
    s = sqrt_int(p)
    c = 2 * (s - 1)
    if s == 0:
        print(0)
        continue
    if mi <= s - 1:
        c -= 1
    r = p // s
    if r > s:
        if s == mi:
            c += 1
        else:
            c += 2
    elif r == s and s != mi:
        c += 1
    print(c)

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
a = [0] * q
b = [0] * q

for i in range(0, q):
    a[i], b[i] = [int(i) for i in input().split(" ")]
    
def sqrt_int(n):
    s = math.floor(n**(1/2)) - 1
    while s * s < n:
        s += 1
    return s - 1

def div_int(p, q):
    r = math.floor(p / q) - 1
    while q * r < p:
        r += 1
    return r - 1

for i in range(0, q):
    mi = min(a[i], b[i])
    mx = max(a[i], b[i])
    p = mi * mx - 1
    s = sqrt_int(p)
    c = 2 * (s - 1)
    if s == 0:
        print(0)
        continue
    if mi <= s - 1:
        c -= 1
    r = div_int(p, s)
    if r > s:
        if s == mi:
            c += 1
        else:
            c += 2
    elif r == s and s != mi:
        c += 1
    print(c)

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
a = [0] * q
b = [0] * q

for i in range(0, q):
    a[i], b[i] = [int(i) for i in input().split(" ")]

for i in range(0, q):
    mi = min(a[i], b[i])
    mx = max(a[i], b[i])
    p = mi * mx - 1
    s = p**(1/2)
    c = 2 * math.floor(s - 1)
    if math.floor(s) == 0:
        print(0)
        continue
    if mi <= math.floor(s - 1):
        c -= 1
    if math.floor(p / math.floor(s)) > math.floor(s):
        if math.floor(s) == mi:
            c += 1
        else:
            c += 2
    elif math.floor(p / math.floor(s)) == math.floor(s) and math.floor(s) != mi:
        c += 1
    print(c)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
for _ in range(n):
  a,b = input().split(" ")
  a,b = sorted([int(a), int(b)])
  c = math.ceil((a*b)**0.5)-1
  print(2*c-(a!=b)-(c*(c+1)>=b*b))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
for _ in range(n):
  a,b = input().split(" ")
  a,b = sorted([int(a), int(b)])
  c = int((a*b)**0.5)
  print(2*c-1-(a==b))

Submission status: Wrong Answer

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

for r in Ri:
    a = r[0]
    b = r[1]
    if a > b:
        t = b
        b = a
        a = t
    max_score = a * b

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