Problem:


Score : 700 points

Problem Statement

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

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

Process the following Q queries:

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

Constraints

1 \leq Q \leq 100

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
A_1 B_1
:
A_Q B_Q

Output

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

Sample Input 1

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

Sample Output 1

1
12
4
11
14
57
31
671644785

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

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



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


Sample output:
1
12
4
11
14
57
31
671644785

Submission status: Accepted

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

import sys

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

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

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

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

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

Submission status: Accepted

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

import sys

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

def calc(x):
    lim=a*b-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**18
    while low+1<hi:
        mid=(hi+low)//2
        if calc(mid):
            hi=mid
        else:
            low=mid
    print(low-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
Q = int(sys.stdin.readline())
A = [0]*Q
B = [0]*Q
for i in range(Q):
    A[i], B[i] = list(map(int, sys.stdin.readline().split()))


def f(a, b, d):
    """
    a, a+1, ..., b と d, d-1, ..., d-(b-a)
    積から、最大のものを返す
    """
    kosu = b-a+1
    wa = d+a
    if wa//2 < a:
        return a*d

    elif wa//2 < b:
        return b*(wa//2-b)

    else:
        return b*d-(b-a)


for i in range(Q):
    if A[i] == B[i]:
        print(2*(A[i]-1))
        continue
    a = min(A[i], B[i])
    b = max(A[i], B[i])
    # print("(A[i], B[i]) = ({},{})".format(a, b))
    c = math.ceil(math.sqrt(a*b))-1
    # print("C={}".format(c))
    if c*(c+1) < a*b:
        print(2*c-1)
    else:
        print(2*c-2)

Submission status: Accepted

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-1))
  else:
    a, b = min(a,b), max(a,b)
    sq = int((a*b)**0.5)
    print(a-1 + sq - a + (a*b-1)//sq -1)

Submission status: Accepted

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 = (n,1)
            second_2 = (0,0)
        else:
            second_1 = (b-1,1)
            second_2 = (n+1, b+1)
        m = (second_2[0] - second_2[1])+1
        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]
            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]
            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]
            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]
            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 = 0
    high = 10**30
    while high - low > 1:
        if check(a,b,(low+high)//2):
            low = (low+high)//2
        else:
            high = (low+high)//2
    return high if check(a,b,high) else low

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

Submission status: Accepted

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

Solution code:
q = int(input())
a = [list(map(int,input().split())) for _ in range(q)]
import math
def f(a,b):
    k = int(math.sqrt(a*b))
    if k>=math.sqrt(a*b):
        k-=1
    if a==b:
        k = 2*min(a,b)-2
    elif min(a,b)+1==max(a,b):
        k = 2*min(a,b)-2
    else:
        if k*(k+1)>=a*b:
            k = 2*k-2
        else:
            k = 2*k-1
    return k
for a_ in a:
    print(f(a_[0],a_[1]))

Submission status: Accepted

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 = math.floor(p**(1/2))
    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: Accepted

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

for A,B in AB:
    x = math.sqrt(A*B)
    y = int(x)
    if x!=y:
        if y*(y+1)<A*B:
            print(y*2-1)
        else:
            print(y*2-2)
    else:
        if A==B:
            print(y*2-2)
        else:
            print(y*2-3)

Submission status: Accepted

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)>=a*b))

Submission status: Accepted

Solution code:
from math import sqrt


def solve(string):
    q, *ab = map(int, string.split())
    ans = []
    for a, b in zip(ab[::2], ab[1::2]):
        c = a * b
        d = int(sqrt(c))
        answer = 2 * d - 2
        if d * d == c:
            answer -= 1
        if d * (d + 1) < c:
            answer += 1
        if a == b:
            answer += 1
        ans.append(str(answer))
    return "\n".join(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
q = int(input())

def f(A,B,x):
    return x*B//(x+A) + 1
def F(A,B):
    st = 1
    ed = B-A-1
    gap = B-A
    maxst = 1
    while st<ed:
        bar = (st+ed)//2
        if f(A,B,bar) + bar <=gap:
            maxst = max(maxst,bar)
            st = bar + 1
        else:
            ed = bar - 1
    if f(A,B,st) + st<=gap:
        maxst = max(maxst,st)
    if f(A,B,maxst)+maxst > gap:
        return -1
    return maxst  
def solveAB(A,B):
    res = 0
    res += (A-1)*2
    st = F(A,B)
    #print(st)
    if st == -1:
        if B-A <2:
            return res
        else:
            return res+1
    if f(A,B,st)+st == B-A and (st-1)*2+1 == B-A-1:
        #print("odd and full")
        res += (st-1)*2+1
    elif f(A,B,st)+st < B-A and st*2 == B-A-1:
        #print("even and full")
        res += st*2
    elif f(A,B,st)+st < B-A and st*2 < B-A-1: 
        #print("even not full")
        res += st*2 + 1
    elif f(A,B,st)+st == B-A and (st-1)*2+1 <B-A-1:
        #print("odd not full")
        res += (st-1)*2+1+1
    return res 
     

for _ in range(q):
    a,b = map(int,input().split())
    A = min(a,b)
    B = max(a,b)
    print(solveAB(A,B))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    s = S()
    a = s.count("a")
    b = s.count("b")
    c = 3-a-b
    if a&b&c:
        print("Yes")
    else:
        print("No")
#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(a,b-k+1),b+1):
        ans.append(i)
    ans = list(set(ans))
    ans.sort()
    for i in ans:
        print(i)

#C
def C():
    a,b,c = LI()
    ans = 0
    if a%2:
        if b%2:
            if not c%2:
                ans += 1
                a += 1
                b += 1
        else:
            ans += 1
            if not c%2:
                b += 1
                c += 1
            else:
                a += 1
                c += 1
    else:
        if b%2:
            ans += 1
            if not c%2:
                a += 1
                c += 1
            else:
                b += 1
                c += 1
        else:
            if c%2:
                ans += 1
                a += 1
                b += 1
    ans += (3*max(a,b,c)-a-b-c)//2
    print(ans)
#D
def D():
    q = I()
    for i in range(q):
        a,b = LI()
        x = int((a*b)**0.5)
        y = math.ceil((a*b)/x)-1
        ans = x+y-2
        if a==b:
            ans += 1
        print(ans)

#E
def E():
    s = S()
    f = {"N":0,"W":0,"S":0,"E":0}
    for i in s:
        f[i] = 1
    if f["N"]^f["S"]:
        print("No")
    elif f["W"]^f["E"]:
        print("No")
    else:
        print("Yes")
#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

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 == r:
            rn -= 1
        if rn * (rn + 1) >= max_score:
            print(2 * rn - 2)
        else:
            print(2 * rn - 1)

Submission status: Accepted

Solution code:
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:
        print((A - 1) + (B - 1))
        continue

    ok, ng = 0, A + B - 1
    while abs(ok - ng) > 1:
        K = (ok + ng) // 2
        m = (K + 2) // 2

        if m * (K + 2 - m) < A * B:
            ok = K
        else:
            ng = K

    print(ok)

Submission status: Accepted

Solution code:
def upper_square(A: int, B: int) -> int:
    """C**2 < A*B を満たす最大の C を求めます。
    """
    l, r = min(A, B), max(A, B)
    while r - l > 1:
        m = (l + r) // 2
        if m * m < A * B:
            l = m
        else:
            r = m
    return l


def query(A: int, B: int) -> int:
    A, B = min(A, B), max(A, B)
    if A == B:
        # (1, 2A-1), ..., (A-1, A+1), (A+1, A-1), ..., (2A-1, 1)
        # が最大。
        return 2 * A - 2
    if B == A + 1:
        # (1, 2A), ..., (A-1, A+2), (A+2, A-1), ..., (2A, 1)
        # が最大。
        return 2 * A - 2

    # C = A
    # while (C + 1) ** 2 < A * B:
    #     C += 1
    C = upper_square(A, B)

    if A * B <= C * (C + 1):
        # (1, A+B−1), ..., (A−1, B+1), (A+1, 2C−A−1), ..., (C, C), ..., (2C−1, 1)
        # が最大。
        return 2 * C - 2

    # (1, A+B−1), ..., (A−1, B+1), (A+1, 2C−A), ..., (C, C+1), (C+1, C), ...,(2C, 1)
    # が最大。
    return 2*C - 1


def worst_case(Q: int, queries: list) -> list:
    return [query(A, B) for A, B in queries]


if __name__ == "__main__":
    Q = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]
    ans = worst_case(Q, queries)
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
q = int(input())
quest = [tuple(map(int, input().split())) for _ in range(q)]
for a, b in quest:
    m = a*b
    l = int((m - 1) ** (1/2))
    # check float
    if l * l >= m:
        l -= 1
    elif (l+1) * (l+1) < m:
        l += 1
    if a == b:
        print((a-1) * 2)
    elif (l+1) * l < m:
        print(l*2 - 1)
    else:
        print(l*2 - 2)

Submission status: Accepted

Solution code:
#import random

q=int(input())
A=[]
for i in range(q):
    A.append(list(map(int,input().split())))
    A[i].sort()

#A=[]
#q=10000
#for i in range(q):
#    A.append([random.randint(1,1000000)]*2)
#    A.sort()
#print(A)

for i in range(q):
    a=A[i][0]
    b=A[i][1]
    if a==b :
        ans1=2*(a-1)
    elif a+1==b :
        ans1=2*a-2
    else :
        c=int((a*b-1)**0.5)+2
        while c*c>=a*b :
            c-=1
        #print("c "+str(c))
        if c*(c+1)>=a*b :
            ans1=2*c-2
        else :
            ans1=2*c-1

    print(ans1)

Submission status: Accepted

Solution code:
import math

q = int(input())
for i in range(q):
    a,b = map(int,input().split())
    x = min(a,b)
    y = max(a,b)
    
    if x <= y <= x+1:
        print((x-1)*2)
    else:
        xy = math.ceil((x*y)**0.5)
        l = xy
        r = xy
        if l*r < x*y:
            print((r-1)*2)
            continue
        r -= 1
        if l*r < x*y:
            print(r*2-1)
            continue
            
        print((r-1)*2)

Submission status: Accepted

Solution code:
# D
q = int(input())

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

for i in range(q):
    k=min(a[i],b[i])
    score=a[i]*b[i]
    sqrt=int(score**0.5)
    if abs(a[i]-b[i])<=1:
        ans=(k-1)*2
    elif sqrt**2==score:
        ans=sqrt*2-3
    elif sqrt*(sqrt+1)>=score:
        ans=(sqrt-1)*2
    else:
        ans=sqrt*2-1
    print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
Q = int(input())
qs = [ tuple(map(int, input().split())) for _ in range(Q)]
for i in range(Q):
    # A,B = map(int, input().split())
    A,B = qs[i]
    A,B = min(A,B), max(A,B)
    if A == B:
        C = A
        print(2*(C-1))
    elif B == A+1:
        C = A
        print(C-1 + C-1)

    else:
        C = int( (A*B)**(1/2))
        if C**2 == A*B:
            C=C-1

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



        continue
        C = A
        n = B - C
        ans = C-1
        # print("NONE")

        MIN = 1
        MAX = B-1 +1 # CANNOT BE
        middle = (MIN+MAX)//2

        # i = (MIN+MAX)//2
        i = middle
        # while (A*B)//(i+1) >= A+1 and not ((A*B//i != (A*B)//(i+1))and(A*B//(i+1) != A*B//(i+2))): # (A*B)//i != (A*B)//(i+1) and (A*B)//(i+1) >= A+1 :

        # while (A*B)//(i+1) >= A+1 and MAX - MIN > 1: # (A*B)//i != (A*B)//(i+1) and (A*B)//(i+1) >= A+1 :
        while MAX - MIN > 1: # (A*B)//i != (A*B)//(i+1) and (A*B)//(i+1) >= A+1 :
            if (A*B-1) // i != (A*B-1)//(i+1) and (A*B-1)//i >= A+1:
                MIN = middle
                i = middle = (MIN+MAX)//2
            else:
                MAX = middle
                i = middle = (MIN+MAX)//2
                

        print("min: {}, max: {}".format(MIN, MAX))
        print(ans + i)
            

        # s = set()
        # for i in range(1,1+C+n):
        #     if (A*B//i) in s:
        #         break
        #     else:
        #         s.add(A*B//i)
        # ans += i
        # print(ans)

Submission status: Accepted

Solution code:
#D
q=int(input())
C=[]
for i in range(q):
    C.append(list(map(int, input().split())))
for i in C:
    k=min(i[0],i[1])
    score=i[0]*i[1]
    sqrt=int(score**0.5)
    if abs(i[0]-i[1])<=1:
        ans=(k-1)*2
    elif sqrt**2==score:
        ans=sqrt*2-3
    elif sqrt*(sqrt+1)>=score:
        ans=(sqrt-1)*2
    else:
        ans=sqrt*2-1
    print(ans)

Submission status: Accepted

Solution code:
import math

Q = int(input())

D = []
for i in range(Q):
  D.append(list(map(int, input().split())))
           
for i in D:
  t = i[0] * i[1]
  l = int(t**0.5)
  if i[0] == i[1]:
    Ans = (l - 1) * 2
  elif l * l == t:
    Ans = (l - 1) * 2 - 1
  elif l * (l + 1) >= t:
    Ans = (l - 1) * 2
  else:
    Ans = l * 2 - 1
  print(Ans)

Submission status: Accepted

Solution code:
q = int(input())

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

    lb, ub, ab = a, 2*b, a*b
    while ub-lb > 1:
        mid = (lb+ub)//2
        """
        1<= k <= xとした時の
        k(x+1-k)の最大値を取るのはk = (x+1)//2の時
        !!!k(x-k)ではない!!!
        これだとk=xで0になってしまう
        """
        maxp = (mid+1)//2*(mid+1-(mid+1)//2)
        if maxp < ab:
            lb = mid
        else:
            ub = mid
    #高橋くんが1つ使っているので1引く
    return lb-1

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

Submission status: Accepted

Solution code:
q = int(input())

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

    lb, ub, ab = a, 2*b, a*b
    while ub-lb > 1:
        mid = (lb+ub)//2
        maxp = (mid)//2*(mid-(mid)//2)
        if maxp < ab:
            lb = mid
        else:
            ub = mid
    return lb-2

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

Submission status: Accepted

Solution code:
q = int(input())

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

    lb, ub, ab = a, 2*b, a*b
    while ub-lb > 1:
        mid = (lb+ub)//2
        maxp = (mid+1)//2*(mid+1-(mid+1)//2)
        if maxp < ab:
            lb = mid
        else:
            ub = mid
    return lb-1

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

Submission status: Accepted

Solution code:
Q = int(input())


def solve(a, b):
    if a == b:
        return 2 * a - 2
    if b < a:
        return solve(b, a)
    lb, ub, ab = a, 2 * b, a * b
    while 1 < ub - lb:
        mid = (lb + ub) // 2
        maxp = (mid + 1) // 2 * (mid // 2 + 1)
        if maxp < ab:
            lb = mid
        else:
            ub = mid
    return lb - 1

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

Submission status: Accepted

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

def main():
    Q = int(input())
    A = []
    B = []
    for i in range(Q):
        na = list(map(int, input().split()))
        A.append(na[0])
        B.append(na[1])

    for i in range(Q):
        a, b = A[i], B[i]

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

        c = a * b
        d = int(math.sqrt(c))
        if d * (d + 1) < c:
            print(d * 2 - 1)
        elif d ** 2 == c:
            print(d * 2 - 3)
        else:
            print(d * 2 - 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q = int(input())
for q in range(Q):
    A, B = map(int, input().split())
    A, B = min(A, B), max(A, B)
    
    # コーナーケース
    if A == B:
        print(2 * (A - 1))
        continue

    # にぶたん: K組作れるか
    ok, ng = 0, A + B - 1
    while abs(ok - ng) > 1:
        K = (ok + ng) // 2
        m = (K + 2) // 2

        if m * (K + 2 - m) < A * B:
            ok = K
        else:
            ng = K

    print(ok)

Submission status: Accepted

Solution code:
# Mister様のblogを参考にいたしました
# https://misteer.hatenablog.com/entry/ARC094-D
Q = int(input())
for q in range(Q):
    A, B = map(int, input().split())
    A, B = min(A, B), max(A, B)

    ok, ng = 0, 10 ** 9 + 1
    while abs(ok - ng) > 1:
        K = (ok + ng) // 2
        m = (A + K) // 2

        # コーナーケース
        if K == A:
            m -= 1

        if m * (A + K - m) < A * B:
            ok = K
        else:
            ng = K

    print(A + ok - 2)

Submission status: Accepted

Solution code:
import math
def near_sqrt(a,b):
  c = a * b
  d = math.floor(math.sqrt(c))
  if d*(d+1) < c:
    return d
  else:
    return (d-1)
  
q = int(input())
for i in range(q):
  a,b = map(int, input().split())
  c = near_sqrt(a,b)
  d = (a*b)%(c+1)
  if d == 0 and a!=b:
    print(math.floor((a*b)/(c+1))+c-2)
  else:
    print(math.floor((a*b)/(c+1))+c-1)

Submission status: Accepted

Solution code:
import math
Q = int(input())
for i in range(Q):
  a, b = map(int, input().split())
  sqrt = int(math.sqrt(a * b))
  sqrt2 = sqrt + 1 if sqrt * (sqrt + 1) < a * b else sqrt
  sub = 1 if sqrt == max(a, b) or sqrt2 == min(a, b) or sqrt * sqrt2 == a * b else 0
  add = min(max(sqrt2 - min(a, b) - 1, 0), max(max(a, b) - sqrt - 1, 0))
  print(min(a, b) - 1 + sqrt + add - sub)

Submission status: Accepted

Solution code:
import math

q = int(input())
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

def doublecount(dc, i):
    if dc >= s[i][0] and dc >= s[i][1]:
        return -2
    elif dc >= s[i][0] or dc >= s[i][1]:
        return -1
    else:
        return 0


count = 0
for i in range(q):
    t = int(math.sqrt(s[i][0] * s[i][1]))
    if t * (t + 1) < s[i][0] * s[i][1]:
        count = t * 2
        count += doublecount(t, i)
        print(count)
    else:
        if t * t < s[i][0] * s[i][1]:
            count = t * 2 - 1
            count += doublecount(t, i)
            print(count)
        else:
            count = (t - 1) * 2
            count += doublecount(t - 1, i)
            print(count)

Submission status: Accepted

Solution code:
import math

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

for A,B in AB:
    x=math.sqrt(A*B)
    y=int(x)
    if x!=y:
        y=int(x)
        if y*(y+1)<A*B:
            print(y*2-1)
        else:
            print(y*2-2)
    else:
        if A==B:
            print(y*2-2)
        else:
            print(y*2-3)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt

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

q = ni()
query = [tuple(li()) for _ in range(q)]

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

Submission status: Accepted

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

def cn(A,B):
    score = A*B-1
    L = A+1
    R = score
    if L>R:
        return 0
    while L!=R:
        tmp = (L+R)//2
        if score > tmp*(tmp+1):
            L = tmp+1
        else:
            R = tmp
    return (L-1-A+score//L)
for ab in AB:
    print(cn(ab[0],ab[1])+cn(ab[1],ab[0]))

Submission status: Accepted

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

for a, b in ab:
    a, b = min(a, b), max(a, b)
    p = a*b
    n = math.ceil((-1+(1+4*p)**(1/2))/2)
    if a <= n:
        lower1 = a-1

    if b <= n:
        lower2 = b-1
    else:
        m = p//n if p%n > 0 else p//n-1
        n_lim = p//(a+1) if p%(a+1) > 0 else p//(a+1)-1
        if n > n_lim:
            lower2 = n_lim
        else:
            lower2 = n + m - (a+1)
            
    print(lower1+lower2)

Submission status: Accepted

Solution code:
Q = int( input())
def matching(A,B):
    #最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる
    #このとき、これらの積の最大値は(x+1)//2*(x+1-(x+1)//2)である
    #ここで、B = A + nであるとき、最大はA*(A+(n-1))以上になることが分かる。
    #n >= 1であれば、積の最大値はA.Bを飛ばしても実現されることが分かる。
    if A == B:
        return 2*A - 2
    S = A*B
    L, H = 0, A*B
    while H - L != 1:
        M = (L+H)//2
        if ((M+1)//2)*(M + 1 - (M+1)//2) < S:
            L = M
        else:
            H = M
    return L-1 #L-1なのは、A,Bを飛ばすため
for _ in range(Q):
    A, B = map( int, input().split())
    print( matching(A,B))

Submission status: Accepted

Solution code:
#from abc093/submissions/2330255
q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    c=int((a*b)**0.5)
    if c*(c+1)<a*b: print(2*c-1)
    elif a*b==c*c and a!=b: print(2*c-3)
    else: print(2*c-2)

Submission status: Accepted

Solution code:
def min_square(min_,max_,AB):
    mid=(min_+max_)//2
    if max_-min_<=1:
        if mid**2<AB:
            return mid
        else:
            return mid-1
    if mid**2 < AB:
        return min_square(mid,max_,AB)
    elif mid**2>AB:
        return min_square(min_,mid,AB)
    else:
        return mid-1

Q=int(input())
for i in range(Q):
    AB=list(map(int,input().split()))
    if AB[0]==AB[1]:
        print((AB[0]-1)*2)
        continue
    mid = min_square(min(AB),max(AB),AB[0]*AB[1])
    if mid*(mid+1)<AB[0]*AB[1]:
        print(mid*2-1)
    else:
        print(mid*2-2)

Submission status: Accepted

Solution code:
def calc_max(a, b, n):
    if n == 0:
        return 0
    m = (b - a) // 2
    if m < 0:
        return a*b
    elif m < n:
        return (a+m)*(b-m)
    else:
        return (a+(n-1))*(b-(n-1))


def judge(a, b, m, x):
    max_value = 0
    if x == 0:
        pass
    elif x < a and x < b:
        max_value = calc_max(1, x, x)
    elif x >= a and x < b:
        max_value = max(calc_max(1, x, a-1),
                        calc_max(a+1, x-(a-1), x-(a-1)))
    else:
        max_value = max(calc_max(1, x+1, x+1-b),
                        calc_max(x + 1-b+1, b-1, a-(x+1-b+1)),
                        calc_max(a+1, x+1-a, x+1-a))
    return True if max_value < m else False


def bs(a, b):
    m = a * b
    lft = 0
    rgt = m
    nxt, prv = -1, -1
    while True:
        nxt = (lft + rgt) // 2
        if nxt == prv:
            return nxt
        if judge(a, b, m, nxt):
            lft = nxt
        else:
            rgt = nxt
        prv = nxt


Q = int(input())
for _ in range(Q):
    A, B = map(int, input().split())
    if A > B:
        A, B = B, A
    print(bs(A, B))