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:
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
  if a==b:
    print(2*a-2)
    continue
  t=floor((a*b)**0.5)
  # t,t+1 組み合わせの積がa*bで抑えられているかどうか
  if t*t>=a*b: # t*tもだめ
    print(2*t-3)
  elif t*(t+1)>=a*b: # t*(t+1)はだめ
    print(2*t-2)
  else: # t*tもt*(t+1)もOK
    print(2*t-1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# C^2 と A*Bの比較
Q = ir()
answer = []
for _ in range(Q):
    a, b = lr()
    if a > b:
        a, b = b, a
    if a == b:
        ans = (a-1) * 2
    elif b == a+1:
        ans = 2 * (a-1)
    elif b > a + 1:
        c = int((a*b-1) ** .5) - 2
        while (c+1) ** 2 < a*b:
            c += 1
        # c は aより大きい
        if c * (c+1) >= a * b:
            ans = 2 * c - 2
        else:
            ans = 2 * c - 1
    answer.append(ans)

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

Submission status: Accepted

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

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):
    if a > b:
        a, b = b, a
    if a == b:
        return 2 * (a - 1)
    t = binsearch(1, a * b, lambda x: (x + 1) // 2 * (x // 2 + 1) < a * b)
    return t - 1

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

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
ans = []
def sub(a,b):
    if a==b:
        ans = 2*a-2
    elif abs(a-b)==1:
        ans = min(a,b)*2-2
    else:
        l = 0
        r = a*b
        while l<r-1:
            m = (l+r)//2
            if m**2<a*b:
                l = m
            else:
                r = m
        a,b = max(a,b), min(a,b)
        ans = 2*l-2
        if l*(l+1)<a*b:
            ans += 1
    return ans
    
for i in range(q):
    a,b = map(int, input().split())
    ans.append(sub(a,b))
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import math

Q = int(input())

for i in range(Q):
  A, B = map(int, input().split())
  ABsq = math.ceil((A*B)**(1/2))
  if A == B:
    print(2*(A-1))
  else:
    if ABsq*(ABsq-1) >= A*B:
      print(2*(ABsq-1)-2)
    else:
      print(2*(ABsq-1)-1)

Submission status: Accepted

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

def solve(a, b):
  ok = 0
  ng = b
  while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(a, b, mid):
      ok = mid
    else:
      ng = mid
  return a - 1 + ok

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    Q=int(input())
    for _ in range(Q):
        a,b=map(int,input().split())
        if a==b:
            print(a+b-2)
            continue
        
        ans=0
        if a<b:
            a,b=b,a
        ans+=b-1
        def nibutan(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve(mid):
            return mid**2<a*b
        
        sq=nibutan(0,10**9)
        if sq*(sq+1)<a*b:
            p,q=sq,sq+1
        else:
            p,q=sq,sq
        ans+=q-b
        ans+=p-1
        print(ans)
        
                

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
q=int(input())
A=[]
for i in range(q):
    a,b=map(int,input().split())
    p=max(a,b)
    q=min(a,b)
    ans=q-1
    if p-q==1:
        now=q-1
    else:
        now=p-1
    if q>now:
        ans+=now
    else:
        s=int(math.sqrt(a*b))
        if s*(s+1)<a*b:
            ans+=(s-q+1)+s-1
        elif s*s<a*b:
            ans+=(s-q+1)+s-2
        else:
            ans+=(s-1-q+1)+s-2
    A.append(ans)
print(*A,sep="\n")

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
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)
    criteria=a*b
    left,right=a,b
    while right>left+1:
        mid=(left+right)//2
        if mid**2>criteria:right=mid
        else:left=mid

    cnt,point=0,0
    for i,j in enumerate(combinations_with_replacement([left,right],2)):
        if point<j[0]*j[1]<=criteria:
            point=j[0]*j[1]
            cnt=i

    if cnt==0:
        if point==criteria and a!=b:print((left-1)*2-1)
        else:print(left*2-2)
    else:
        if point==criteria:print(left*2-2)
        else:print(left*2-1)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
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)
    criteria=a*b
    left,right=a,b
    while right>left+1:
        mid=(left+right)//2
        if mid**2>criteria:right=mid
        else:left=mid

    cnt,point=0,0
    for i,j in enumerate(combinations_with_replacement([left,right],2)):
        if point<j[0]*j[1]<=criteria:
            point=j[0]*j[1]
            cnt=i

    #print(left,right)
    if cnt==0:
        if point==criteria:
            if a!=b:print((left-1)*2-1)
            else:print(left*2-2)
        else:print(left*2-2)
    else:
        if point==criteria:print(left*2-2)
        else:print(left*2-1)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
Q = int(input())

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

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

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

    if C.is_integer():
        D -= 1

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

    ans.append(F)

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

Submission status: Accepted

Solution code:
Q = int(input())

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

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

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

Solution code:


q = int(input())
info = [list(map(int, input().split())) for i in range(q)]

for i in range(q):
    min_, max_ = info[i]
    min_, max_ = min(min_, max_), max(min_, max_)
    
    # a, b = 1, 1 のときREが出る
    if min_ == 1 and max_ == 1:
        print(0)
        continue

    mul = min_ * max_
    ans = 2 * (min_ - 1)

    ok = 0
    ng = max_ + 10
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if mid <= (mul - 1) // mid:
            ok = mid
        else:
            ng = mid
    ans += max(ok - (min_ - 1), 0)
    ans += max(ok - min_, 0)
    
    if ok == (mul - 1) // ok:
        ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
data = int(input())

def solve(nim,mike):
    if nim == mike:
        return 2*nim-2
    if mike < nim:
        return solve(mike, nim)

    lb, ub, ab = nim, 2*mike, nim*mike
    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(data):
    nim, mike = map(int, input().split())
    print(solve(nim,mike))

Submission status: Accepted

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):
        a = sqrt(Ai * Bi)
        b = a + 1 if a * (a + 1) <= Ai * Bi else a

        def f(a: int, b: int):
            m = a + b - 2
            if a * b == Ai * Bi:
                m -= b - a + 1
                if {a, b} == {Ai, Bi}:
                    m += 1
            return m

        print(max(f(a, b), f(a, b - 1)))


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

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

Q = int(input())
for _ in range(Q):
    A, B = map(int, input().split())
    if A > B:
        A, B = B, A
    ans = (A - 1) * 2
    lb, ub = A, B
    while ub - lb > 1:
        m = (lb + ub) // 2
        x = (A+1+m) // 2
        if (m - A) % 2 == 0:
            if x*x >= A*B:
                ub = m
            else:
                lb = m
        else:
            if x*(x-1) >= A*B:
                ub = m
            else:
                lb = m
    ans += lb - A
    print(ans)

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 - 2)
        continue

    l = 1
    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 - 1)

Submission status: Accepted

Solution code:
eps = 10**-7

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

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

Submission status: Accepted

Solution code:
from math import sqrt

eps = 10**-7

def check(a, b):
  if b < a:
    a, b = b, a
  if b - a <= 1:
    return 2 * a - 2
  c = int(sqrt(a*b) - eps)
  assert(c**2 < a*b <= (c+1)**2)
  return 2 * c - 1 - (c * (c + 1) >= a * b)

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

Submission status: Accepted

Solution code:
def check(a, b):
  if b < a:
    a, b = b, a
  if b - a <= 1:
    return 2 * a - 2
  d = a * b
  c, ng = a, b
  while ng - c > 1:
    mid = (ng + c) // 2
    if mid ** 2 < d:
      c = mid
    else:
      ng = mid
  return 2 * c - 1 - (c * (c + 1) >= a * b)

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

Submission status: Accepted

Solution code:
from math import ceil, floor

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


def f(a, b, x):
    return (a + x - 1) * (b - x + 1)


def get_mx(a, b, num):
    tmp = (b - a + 2) / 2
    lx = max(1, floor(tmp))
    rx = min(num, ceil(tmp))
    mx = max(f(a, b, lx), f(a, b, rx))
    return mx


def check(a, b, num):
    mx = 1
    a, b = min(a, b), max(a, b)
    if num < a:
        mx = max(mx, get_mx(1, num, num))
    elif a <= num < b:
        mx = max(mx, get_mx(1, num, a - 1))
        mx = max(mx, get_mx(a + 1, num - a + 1, num - a + 1))
    elif num >= b:
        if num - b + 1 > a - 1:
            mx = max(mx, get_mx(1, num + 1, a - 1))
            mx = max(mx, get_mx(a + 1, num - a - 2, num - a - b + 2))
            mx = max(mx, get_mx(num - b - 2, b - 1, b - 1))
        elif num - b + 1 == a - 1:
            mx = max(mx, get_mx(1, num + 1, a - 1))
            mx = max(mx, get_mx(a + 1, b - 1, b - 1))
        else:
            mx = max(mx, get_mx(1, num + 1, num - b + 1))
            mx = max(mx, get_mx(num - b + 2, b - 1, a + b - num - 2))
            mx = max(mx, get_mx(a + 1, num - a + 1, num - a + 1))

    if mx < a * b:
        return True

    return False


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
        if check(a, b, m):
            l = m
        else:
            r = m

    print(l)

Submission status: Accepted

Solution code:
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    if a == b:
        print(2 * (a - 1))
        continue
    if a > b:
        a, b = b, a
    ans = a - 1

    l, r = -1, b - 1
    while r - l > 1:
        k = (l + r) // 2
        x = min(k, (a + 1 + k) // 2)
        y = (a + 1 + k) - x
        if x * y < a * b:
            l = k
        else:
            r = k
    ans += l
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# 高橋君のスコア：a*b(a<b)とする
# 1~a-1 は b+a-1~b+1 と組み合わせればok
# a は b-1 と組み合わせればok
# [a+1,b-2]*2 から何ペアできるか二分探索

Q = I()
A,B = LIR(Q,2)

for i in range(Q):
    a,b = min(A[i],B[i]), max(A[i],B[i])
    ab = a*b
    if b-a <= 1:
        print(2*(a-1))
    else:
        ok = 0
        ng = b-a-1
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if mid%2 == 0:
                max_val = (a+mid//2)*(a+mid//2+1)
            else:
                max_val = (a+(mid+1)//2)**2
            if max_val < ab:
                ok = mid
            else:
                ng = mid
        print(2*(a-1)+1+ok)

Submission status: Accepted

Solution code:
def can(a, b):
  a, b = min(b, a),max(a,b)
  if b - a <= 1:
    return 2*a-2
  c = int((a*b)**0.5)
  if c**2 == a*b:
    c -= 1
  if c*(c+1) >= a*b:
    return 2*c-2
  return 2*c-1
q = int(input())
for _ in range(q):
  a, b = map(int, input().split())
  print(can(a, b))

Submission status: Accepted

Solution code:
from math import sqrt

Q=int(input())
ans=[]
for i in range(0,Q):
    a,b=map(int,input().split())
    if a!=b:
        r=int(sqrt(a*b))
        if r*(r+1)<a*b:
            ans.append(2*r-1)
        else:
            if r**2==a*b:
                ans.append(2*r-3)
            else:
                ans.append(2*r-2)
    else:
        ans.append(2*a-2)


for i in range(0,Q):
    print(ans[i])

Submission status: Accepted

Solution code:
q=int(input())
def check(t,a,b):
    k=(2*a+t)//2
    return k*(2*a+t-k)<a*b

for i in range(q):
    a,b=sorted(map(int,input().split()))
    if a==b or a==b-1:
        print(2*a-2)
        continue
    l,r=1,b-a
    while l+1<r:
        t=(l+r)//2
        if check(t,a,b):
            l=t
        else:
            r=t
    if check(r,a,b):
        print(2*a-2+r)
    else:
        print(2*a-2+l)

Submission status: Accepted

Solution code:
q=int(input())
def check(t,a,b):
    k=(2*a+t)//2
    return k*(2*a+t-k)<a*b

for i in range(q):
    a,b=sorted(map(int,input().split()))
    if a==b or a==b-1:
        print(2*a-2)
        continue
    l,r=1,b-a
    while l+1<r:
        t=(l+r)//2
        if check(t,a,b):
            l=t
        else:
            r=t
    
    if check(r,a,b):
        print(2*a-2+r)
    elif check(l,a,b):
        print(2*a-2+l)
    else:
        print(2*a-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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
            ok = 0
            ng = int(ab ** 0.5) + 1000000
            while abs(ng - ok) > 1:
                mid = (ok + ng) // 2
                if mid ** 2 < ab:
                    ok = mid
                else:
                    ng = mid
            c = ok

            if c * (c + 1) < ab:
                print(2 * c - 1)
            else:
                print(2 * c - 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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 - A
    cnt += y - 1

    x, y = B, A
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - B
    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: Accepted

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

Submission status: Accepted

Solution code:

"""

(N-1)(N+1) = N^2 - 1
(N-2)(N+2) = N^2 - 4

A,Bが等しいときは、上の式に基づいて2*(A-1)人小さい人を作れる

A,Bが等しくないときは、同じように作るとすると

(A-x)*(B+x) = AB + (A-B)x - x^2
なので、(A-B)x - x^2 < 0 → (A-B) < x
よって、A < B ならば、A-1…1まですべて使用可能。
A>Bならば、 A- (A-B+1) … 1まで使用可能

どちらか片方が高橋君より小さいことは必須→A,B中片方は範囲外の数字で全て無駄なく使ってしまう
残りは使える個数に制限があるけど、できるだけ使ってしまうのでこれで最適かな
→だめだった！！！！

=====けんちょんさんのブログ参照=========

A,Bから小さい方から同じ数だけ使っていくのが最適なのは自明
高橋君のA,Bを除いてA,BからNこずつ取ってくるとする。
最大値を最小化するには、大きい方からx番目と小さい方からx番目をマッチングする
→真ん中らへんに最大値が来るはず
最大値を無理やり求めてあげる→最大値がtA*tBを超えない最大のNを2分探索!!
"""
def kth(m,k):
    if m >= k:
        return m+1
    else:
        return m

def wantmax(m,A,B): #mコとった時の最大値計算(真ん中らへんを探索)

    ret = 0

    for i in range(-10,10):

        now = m // 2 + i
        
        if 0 < now <= m:

            ret = max( ret , kth(now,A) * kth(m-now+1,B) )

    return ret
        
            

Q = int(input())

for loop in range(Q):

    A,B = map(int,input().split())

    l = 0
    r = A*B

    while r -l != 1:
        m = (r+l) // 2

        ret = wantmax(m,A,B)
        #print (m,ret)

        if ret >= A*B:
            r = m
        else:
            l = m

    print (l)

Submission status: Accepted

Solution code:
Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    if A==B:
        print((A-1)*2)
    elif 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: Accepted

Solution code:
from math import sqrt
Q = int(input())
for _ in range(Q):
    a,b = map(int,input().split())
    rank = a*b
    sqrank = int(sqrt(rank))
    ans = 2*sqrank - 2
    if sqrank**2 == rank:
        ans -= 1
    if sqrank*(sqrank+1) < rank:
        ans += 1
    if a == b:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())

def check(x, a, b):
  y = (a <= -(-x // 2)) or (b <= -(-x // 2))
  z = (a <= (x // 2 + 1)) and (b <= (x // 2 + 1))
  return (-(-x // 2) + y) * ((x // 2 + 1) + z) < a * b

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

  ok = 0
  ng = a * b
  while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m, a, b): ok = m
    else: ng = m
  print(ok)

Submission status: Accepted

Solution code:
#1~xまでの整数の組*2の最大マッチングを考える
#基本はx//2と(x+1)//2のマッチングが最大値，a==bに注意

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)
    else:
        ab=a*b
        ok=1
        ng=a*b
        while (ng-ok)>1:
            med=(ok+ng)//2
            if ((med+1)//2) * ((med+2)//2) >=ab:
                ng=med
            else:
                ok=med
        print(ok-1)

Submission status: Accepted

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))
    if c*c==ab:
        c-=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: Accepted

Solution code:
Q = int(input())
def f(a, b, s, i):
    if i == b or i<= 0 or i>s+1:
        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: Accepted

Solution code:
# max(1*(a+n-1), 2*(a+n-2), ..., n*a)
def f(a, n):
  x = min((a+n)/2, n)
  y = a+n-x
  return x*y

Q = input()
for _ in range(Q):
  A, B = map(int, raw_input().split())
  if A>B:
    A,B = B,A
  n = 0
  b = 2**32
  while b>0:
    if f(A+1, n+b)<A*B:
      n += b
    b /= 2
  print A-1+n

Submission status: Accepted

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 s*s>=a*b:
    s=s-1
  if (s+1)*(s+1)<a*b:
    s=s+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: Accepted

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

Submission status: Accepted

Solution code:
def floorsqrt(x):
  max_ok = 0
  min_ng = x+1
  while min_ng-max_ok>1:
    tgt = (max_ok+min_ng)//2
    if tgt*tgt<=x:
      max_ok = tgt
    else:
      min_ng = tgt
  return max_ok

def K1(C, r):
  max_ok = 0
  min_ng = C
  while min_ng-max_ok>1:
    tgt = (max_ok+min_ng)//2
    if C-tgt>r+tgt*tgt:
      max_ok = tgt
    else:
      min_ng = tgt
  return max_ok

def K2(C, r):
  max_ok = 0
  min_ng = C
  while min_ng-max_ok>1:
    tgt = (max_ok+min_ng)//2
    if C-tgt>r+tgt*(tgt+1):
      max_ok = tgt
    else:
      min_ng = tgt
  return max_ok

Q = int(input())
for _ in range(Q):
  A, B = map(int, input().split())
  if A*B==1:
    print(0)
    continue
  if B<A: A,B = B,A
  
  C = floorsqrt(A*B-1)
  #print(A, B, C, C*C, A*B-1, C*C+2*C+1)
  
  # C:= floor(sqrt(AB-1))
  
  q = (A*B-1)//C
  r = (A*B-1)%C

  if q==C:
    # Case 1: (AB-1)//C == C ... r
    # a :    1 ... C     AB-1
    # b : AB-1     C ...    1
    #
    # (AB-1)//(C-k) == C+k ... r+k*k
    # K = max{k | C-k>r+k*k}
    K = K1(C, r)
    ans = 2*C-3 if B<=C+K else 2*C-2
    #print(K, B, C+K)
  
  elif q==C+1:
    # Case 2: (AB-1)//C == C+1 ... r
    # a :    1 ... C   C+1     AB-1
    # b : AB-1     C+1   C...     1
    #
    # (AB-1)//(C-k) == C+k+1 ... r+k*(k+1)
    # K = max{k | C-k>r+k*(k+1)}
    K = K2(C, r)
    ans = 2*C-2 if B<=C+K+1 else 2*C-1
 
  else:
    # Case 3: (AB-1)//C == C+2
    # a :    1 ... C   C+2     AB-1
    # b : AB-1     C+2   C...     1
    ans = 2*C if A==B else 2*C-1
    
  print(ans)

Submission status: Accepted

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)**.5)
        X -= A*B == X*X
        print(2*X-1-(X*(X+1)>=A*B))

Submission status: Accepted

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)
    print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
Q=int(input())
def solv(A,B):
    if A==B:
        return 2*A-2

    if A>B:
        A,B=B,A

    l=A
    r=B*2
    while r-l>1:
        m=(l+r)//2
        x=(m+1)//2*(m//2+1)
        if x<A*B:
            l=m
        else:
            r=m
    return l-1



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

Submission status: Accepted

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)-2
    while (n+1)**2 < N:
        n += 1
    if a == b == 1:
        return 0
    cnta = n
    cntb = n
    if a <= n:
        cnta -= 1
    if b <= n:
        cntb -= 1
    ans = cnta + cntb
    # A : 1,2,3,..,n,n+1, 大きい数
    # B : 大きい数,n+1,n,...,3,2,1
    # それぞれペアを見つけながら進んでいけばいいので基本 2*n
    # 1. Aの1~nまでにaが入っていると-1
    # 2. Bの1~nまでにbが入っていると-1
    # 3. n*n+1がabより大きいと成り立たないので-1
    if n*(n+1) >= N:
        ans -= 1
    return ans        

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

Submission status: Accepted

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
        
        p = a * b
        c = floor(sqrt(p))
        res += (c - a) * 2 + 1
        if c * (c + 1) >= p:
            res -= 1
        if c * c == p:
            res -= 1
        yield res



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

Submission status: Accepted

Solution code:
Q = int(input())
AB = [tuple(map(int, input().split())) for _ in range(Q)]
for A, B in AB:
    C = (A * B)**0.5

    if A == B:
        print(A * 2 - 2)
    else:
        if C.is_integer():
            C -= 1

        C = int(C)

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