TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
from math import sqrt

Q = int(input())

for i in range(Q):
    A,B = map(int, input().split())
    m=A*B
    C = int(sqrt(m))
    if C*C==m:
        C=C-1

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

from math import sqrt

Q = int(input())

for i in range(Q):
    A,B = map(int, input().split())
    m=A*B
    if A==B or B==A+1:
        ans = 2*A-2
    elif A==B+1
        ans = 2*B-2

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

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

from math import sqrt

Q = int(input())

for i in range(Q):
    A,B = map(int, input().split())
    m=A*B
    if A==B or B=A+1:
        ans = 2*A-2
    elif A=B+1
        ans = 2*B-2

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

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

from math import sqrt

Q = int(input())

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

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

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

Verdicts: Wrong Answer

Runtime Error

Runtime Error

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

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

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

Verdicts: Wrong Answer

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

Submission attempts (in order):
n=int(input())

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

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


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

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

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

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


Verdicts: Wrong Answer

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

Submission attempts (in order):
n = int(input())
arr = []
for i in range(n):
    arr.append([int(x) for x in input().split()])
for pair in arr:
    first = {}
    first[pair[0]] = pair[0]
    second = {}
    second[pair[1]] = pair[1]
    pairs = []
    _max = max(pair)
    _min = min(pair)
    total = _max * _min - 1
    for i in range(1, total):
        j = int(total / i)
        if i not in first and j not in second:
            first[i] = i
            second[j] = j
            pairs.append([i, j])
    print(len(pairs))

n = int(input())
arr = []
for i in range(n):
    arr.append([int(x) for x in input().split()])
for pair in arr:
    first = {}
    first[pair[0]] = pair[0]
    second = {}
    second[pair[1]] = pair[1]
    pairs = []
    _max = max(pair)
    _min = min(pair)
    total = _max * _min
    for i in reversed(range(1, total - 1)):
        for j in range(1, total - 1):
            if i not in first and j not in second and i * j < total:
                first[i] = i
                second[j] = j
                pairs.append([i, j])
    print(len(pairs))
                
            
        

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

Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
import math 
Q=int(input())
A=[0 for i in range(Q)]
B=[0 for i in range(Q)]
for i in range(Q):
    A[i],B[i]=map(int,input().split())
for i in range(Q):
    C=A[i]*B[i]
    N=int(math.sqrt(C))
    D=0
    if N**2==C:
        N-=1
    else:
        while(True):
            if A[i]*B[i]<N**2:
                N-=1
            elif A[i]*B[i]>(N+1)**2:
                N+=1
            else:
                break
            print(N)
    M=2*N-1
    print(M)


import math 
Q=int(input())
A=[0 for i in range(Q)]
B=[0 for i in range(Q)]
for i in range(Q):
    A[i],B[i]=map(int,input().split())
for i in range(Q):
    C=A[i]*B[i]
    N=int(math.sqrt(C))
    D=0
    if N**2==C:
        N-=1
    else:
        while(True):
            if A[i]*B[i]<N**2:
                N-=1
            elif A[i]*B[i]>(N+1)**2:
                N+=1
            else:
                break
            print(N)
    M=2*N
    S=M-1
    if M*(M-A[i])>=C and M*(M-B[i])>=C and (M-A[i])*(M-B[i])<C:
        S-=1
    elif A[i]>=M and B[i]<M and M*(M-B[i])>=C:
        S-=1
    elif B[i]>=M and A[i]<M and M*(M-A[i])>=C:
        S-=1
    elif (M-A[i])*(M-B[i])>=C:
        S-=2
    print(S)


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


Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
import math

q = int(input())

for i in range(q):
    a, b = map(int, input().split())
    sq = (a*b)**0.5
    ans = int(math.modf(sq*2 - 2)[1])
    if a < 5 and b < 5:
        ans1 = 0
        ax = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        ax.pop(ax.index(a))
        bx = [9, 8, 7, 6, 5, 4, 3, 2, 1]
        bx.pop(bx.index(b))
        ax1 = []
        bx1 = []
        for ai in ax:
            if ai in ax1:
                continue
            for bi in bx:
                if bi in bx1:
                    continue
                if ai*bi < a*b:
                    ax1.append(ai)
                    bx1.append(bi)
                    ans1 += 1
        print(ans1)
    else:
        print(ans)


import math

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

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

Verdicts: Wrong Answer

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

Submission attempts (in order):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    rr = []
    for _ in range(n):
        a,b = LI()
        t = a*b
        s = int(t ** 0.5)
        if s*s == t:
            rr.append((s-1)*2-1)
        elif s*(s+1) < t:
            rr.append(s*2-1)
        else:
            rr.append((s-1)*2)


    return '\n'.join(map(str, rr))


print(main())




import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    rr = []
    for _ in range(n):
        a,b = LI()
        t = a*b
        s = int(t ** 0.5)
        if t < 3:
            rr.append(0)
        elif a == b:
            if (a-1) * (b+1) < t:
                rr.append((a-1)*2)
            else:
                rr.append((a-1)*2-1)
        elif s*s == t:
            rr.append((s-1)*2-1)
        elif s*(s+1) < t:
            rr.append(s*2-1)
        else:
            rr.append((s-1)*2)


    return '\n'.join(map(str, rr))


print(main())




Verdicts: Wrong Answer

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

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

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

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

if __name__ == '__main__':
    examD()


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

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

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

if __name__ == '__main__':
    examD()


Verdicts: Wrong Answer

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

Submission attempts (in order):
#!python3

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


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

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


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


if __name__ == "__main__":
    main()


#!python3

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


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

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

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


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


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

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

Submission attempts (in order):
import sys
sys.setrecursionlimit(10**6)

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

    def input():
        return infile.readline()


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

from math import sqrt


def main():
    Q = int(input().strip())
    AB = [list(map(int, input().strip().split())) for _ in range(Q)]
    for a, b in AB:
        score = a * b
        root = sqrt(score)
        pivot = int(root)
        cnt = 2 * (pivot - 1) if pivot == root else 2 * (pivot - 1) + 1
        print(cnt)


main()

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

if debug_mode:
    infile.close()


import sys
sys.setrecursionlimit(10**6)

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

    def input():
        return infile.readline()


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

from math import sqrt


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


main()

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

if debug_mode:
    infile.close()


Verdicts: Wrong Answer

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

Submission attempts (in order):
q=int(input())
while q>0:
    q-=1
    a,b=map(int,input().split())
    s=int((a*b)**0.5)
    if s==0:
        print(0)
        continue
    ret=2*s
    if (a*b-1)//s==s:
        ret-=1
    if min(a,b)<=s:
        ret-=1
    print(ret)

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


Verdicts: Wrong Answer

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

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

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

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

Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
# -*- coding: utf-8 -*-

from math import ceil, sqrt

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

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

# -*- coding: utf-8 -*-

from math import ceil, sqrt

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

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

Verdicts: Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
import sys
input = sys.stdin.readline
n = int(input())
ans = 0
flag = 0
for i in range(n):
  a,b = map(int,input().split())
  if a > b:flag = 1
  ans += a
print(ans*flag)


import sys
input = sys.stdin.readline
n = int(input())
m = 10**10
ans = 0
flag = 0
for i in range(n):
  a,b = map(int,input().split())
  if a > b:
    flag = 1
    m = min(m,b)
  ans += a
print((ans-m)*flag)


Verdicts: Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[]
ans=0
for a,b in arr:
  ans+=a
  arr2.append([a-b,b])
arr2=sorted(arr2,reverse=True)
ans=-arr2[0][1]
print(ans)

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[]
ans=0
mb=10**18
for a,b in arr:
  ans+=a
  if a>b:
    mb=min(mb,b)
if mb==10**18:
  print(0)
else:
  print(ans-mb)

Verdicts: Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
n = int(input())
a, b, c = [], [], []
for i in range(n):
    ab = list(map(int, input().split()))
    a.append(ab[0])
    b.append(ab[1])
    if(ab[0] > ab[1]):
        c.append(ab[1])
if(len(c) == 0):
    print(0)
else:
    sort.c()
    print(sum(a) - c[0])

n = int(input())
a, b, c = [], [], []
for i in range(n):
    ab = list(map(int, input().split()))
    a.append(ab[0])
    b.append(ab[1])
    if(ab[0] > ab[1]):
        c.append(ab[1])
if(len(c) == 0):
    print(0)
else:
    print(sum(a) - min(c))

Verdicts: Runtime Error

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
N = int(input())
ans = 0
m = INF = 10**9+7
d = []
for i in range(N):
    a, b = map(int, input().split())
    ans += a
    if a > b:
        m = min(m, b)
print(0 if INF else ans-m)

N = int(input())
ans = 0
m = INF = 10**9+7
d = []
for i in range(N):
    a, b = map(int, input().split())
    ans += a
    if a > b:
        m = min(m, b)
print(0 if INF == m else ans-m)

Verdicts: Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
import sys

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

def main():
    n=int(input())
    ab=[list(map(int, input().split())) for _ in range(n)]
    ab.sort(key=lambda x:x[0]-x[1])
    print(ab)
    re=0
    ans=0
    for a,b in ab:
        if a<b:
            ans+=b
            re+=b-a
        if a>=b:
            if re>=a:
                ans+=b
                re-=a
            else:
                ans+=b-a+re
        #print(a,b,re,ans)
    print(ans)

main()

import sys

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

def main():
    n = int(input())
    min_b = 10 ** 10
    s = 0
    for _ in range(n):
        a, b = map(int, input().split())
        s += b
        if a > b:
            min_b = min(min_b, b)
    print(0) if min_b == 10 ** 10 else print(s - min_b)

main()


Verdicts: Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

c = 0

if A == B:
    print(c)
    exit()


for i in range(N):
    if A[i] < B[i]:
        c += A[i]
        B[i] -= A[i]
        A[i] = 0

while A != B:
    x = 0
    for i in range(N):
        if A[i] == 0:
            continue
        x = i
        if A[i] < B[i]:
            break
    A[x] -= 1
    y = 0
    for i in range(N):
        if A[i] == B[i]:
            continue
        y = i
        if A[i] < B[i]:
            break
    B[y] -= 1
    candy += 1

print(candy)


N = int(input())

same = True
sum_a = 0
min_b = None

for _ in range(N):
    a, b = map(int, input().split())
    
    sum_a += a
    
    if a != b:
        same = False
    
    if a > b and (min_b is None or b < min_b):
        min_b = b


if same:
    print(0)
    exit()


if min_b is None:
    min_b = 0

print(sum_a - min_b)


Verdicts: Runtime Error

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
N = int(input())
c = False
s = 0
for i in range(N):
    ai,bi = map(int,input().split())
    s += ai
    if ai > bi:
        if not C:
            c = bi
        if bi < c:
            c = bi
if not c:
    print(0)
else:
    print(s-c)

N = int(input())
c = -1
s = 0
for i in range(N):
    ai,bi = map(int,input().split())
    s += ai
    if ai > bi:
        if c == -1:
            c = bi
        if bi < c:
            c = bi
if c == -1:
    print(0)
else:
    print(s-c)

Verdicts: Runtime Error

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
n=int(input())
rem=0
S=0
allissame=0
for i in range(n):
  a,b=map(int,input().split())
  S+=a
  if a<b:
    allissame|=1
    continue
  elif a>b:
    if rem > b:
      rem=b
    allissame|=1
  else:pass
if not allissame:
  print(0)
else:
  print(S-rem)


n=int(input())
rem=10**10
S=0
allissame=0
for i in range(n):
  a,b=map(int,input().split())
  S+=a
  if a<b:
    allissame|=1
    continue
  elif a>b:
    if rem < b:
      rem=b
    allissame|=1
  else:pass
if not allissame:
  print(0)
else:
  print(S-rem)


n=int(input())
rem=10**10
S=0
allissame=0
for i in range(n):
  a,b=map(int,input().split())
  S+=a
  if a<b:
    allissame|=1
    continue
  elif a>b:
    if rem > b:
      rem=b
    allissame|=1
  else:pass
if not allissame:
  print(0)
else:
  print(S-rem)


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
N=int(input())
ab=[[int(i) for i in input().split()] for j in range(N)]
total = sum([sum(row) for row in ab])//2
diff = [row[1] for row in ab if row[0]>row[1]]
if len(diff)==0:
    print(0)
else:
    print(total-diff)


N=int(input())
ab=[[int(i) for i in input().split()] for j in range(N)]
total = sum([sum(row) for row in ab])//2
diff = [row[1] for row in ab if row[0]>row[1]]
if len(diff)==0:
    print(0)
else:
    print(total-min(diff))


Verdicts: Runtime Error

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
n = int(input())
s = 0
minb = float("inf")
for _ in range(n):
  a, b = map(int, input().split())
  if a > b:
    minb = min(b, minb)
  s += a
if b == float("inf"):
  print(s - minb)
else:
  print(0)

n = int(input())
s = 0
minb = float("inf")
for _ in range(n):
  a, b = map(int, input().split())
  if a > b:
    minb = min(b, minb)
  s += a
if minb == float("inf"):
  print(0)
else:
  print(s - minb)

Verdicts: Wrong Answer

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
import math

n = int(input())
c = -1
sum_ = 0
for i in range(n):
    a, b = map(int, input().split())
    sum_ += a
    if a > b:
        if c == -1:
            c = b
        if b > c:
            c = b
if c == -1:
    print("0")
else:
    print(s - c)


import math

n = int(input())
c = -1
sum_ = 0
for i in range(n):
    a, b = map(int, input().split())
    sum_ += a
    if a > b:
        if c == -1:
            c = b
        if b < c:
            c = b
if c == -1:
    print(0)
else:
    print(sum_ - c)


Verdicts: Runtime Error

Accepted
Problem: You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.  Tozan and Gezan repeats the following sequence of operations:    * If A and B are equal sequences, terminate the process.   * Otherwise, first Tozan chooses a positive element in A and decrease it by 1.   * Then, Gezan chooses a positive element in B and decrease it by 1.   * Then, give one candy to Takahashi, their pet.  Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Submission attempts (in order):
N = int(input())
diff_a_b = []
for i in range(N):
  a, b = map(int, input().split())
  diff_a_b.append([a - b, a, b])

diff_a_b.sort()
if diff_a_b[0][0] == 0: 
  print(0)
  quit()

ans = 0
d = 0
for diff, a, b in diff_a_b:
  if diff <= 0: # a <= b
    ans += b
    d -= diff
  else:
    if d > diff:
      d -= diff
      ans += b
    else: # d <= diff
      ans += d
      break

print(ans)

N = int(input())
diff_a_b = []
for i in range(N):
  a, b = map(int, input().split())
  diff_a_b.append([a - b, a, b])

diff_a_b.sort()
if diff_a_b[0][0] == 0: 
  print(0)
  quit()

ans = 0
d = 0
temp = 10**10
for diff, a, b in diff_a_b:
  if diff <= 0: # a <= b
    ans += b
    d -= diff
  else:
    ans += b
    temp = min(temp, b)

print(ans - temp)

Verdicts: Wrong Answer

Accepted
Problem: Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible **diverse** words in lexicographical order.  A word is called **diverse** if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, `atcoder`, `zscoder` and `agc` are diverse words while `gotou` and `connect` aren't diverse words.  Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.  Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Submission attempts (in order):
import sys
 
 
alph="abcdefghijklmnopqrstuvwxyz"
allis=list(alph)
S=input()
if(S=="zyxwvutsrqponmlkjihgfedcba"):
    print(-1)
    sys.exit()
 
for i in alph:
    if(i not in S):
        print(S)
        sys.exit()
        
l=-1
for i in range(len(S)-1)[::-1]:
    if(ord(S[i])<ord(S[i+1])):
        l=i
        break
        
x=sorted(S[i+1:])
for i in x:
    if(i>S[l]):
        print(S[:l]+i)
        sys.exit()

inp = input()
inp_len = len(inp)
chars = map(ord,list(inp))
dic = {}
an = ""
if inp == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()
if inp_len == 26:
    for i in range(25):
        if ord(inp[-1 - i]) > ord(inp[-2 - i]):
            an = inp[:-2-i]
            ls = inp[-2-i]
            for char in map(ord,list(inp[-1-i:])):
                dic[char] = "exist"
            break
    for j in range(26):
        if  97 + j in dic and 97+ j  >  ord(ls):
            an =  an + chr(97+j)
            break
else:
    for char in chars:
        dic[char] = "exist"
    for i in range(26):
        if not (97 + i) in dic:
            an =  inp + chr(97+i)
            break
print(an)


Verdicts: Wrong Answer

Accepted
Problem: Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible **diverse** words in lexicographical order.  A word is called **diverse** if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, `atcoder`, `zscoder` and `agc` are diverse words while `gotou` and `connect` aren't diverse words.  Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.  Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Submission attempts (in order):
s=list(input())
al=[chr(ord('a') + i) for i in range(26)]
al=[i for i in al if i not in s]
if al:
    print(s+al[0])
    exit()
for i in range(25,0,-1):
    if s[i-1]<s[i]:
        s=s[:i-1]+[s[-1]]
        print(''.join(s))
        exit()
else:print(-1)

s=input()
al=[chr(ord('a') + i) for i in range(26)]
al=[i for i in al if i not in s]
if not al:
    print(-1)
    exit()
for i,j in enumerate(s):
    if al[0]<j:
        print(s[:i]+al[0]+s[i:])
        break

s=list(input())
al=[chr(ord('a') + i) for i in range(26)]
al=[i for i in al if i not in s]
if al:
    print(''.join(s)+al[0])
    exit()
for i in range(25,0,-1):
    if s[i-1]<s[i]:
        a=[j for j in s[i-1:] if s[i-1]<j]
        s=s[:i-1]+[sorted(a)[0]]
        print(''.join(s))
        break
        exit()
else:print(-1)

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible **diverse** words in lexicographical order.  A word is called **diverse** if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, `atcoder`, `zscoder` and `agc` are diverse words while `gotou` and `connect` aren't diverse words.  Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.  Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Submission attempts (in order):
alp=[chr(ord('a') + i) for i in range(26)]
unused=set(alp)
     
S=input()
print("len",len(S))

if len(S)<26:
    for i in range(len(S)):
        if S[i] in unused:
            unused.remove(S[i])
    unused=sorted(unused)
    print(S+unused[0])
else:
    for j in range(len(S)-1,-1,-1):
        p=set(S[j:])
        #print(p)
        q=sorted(p)
        if S[j]==q[-1]:
            pass
        else:
            idx=q.index(S[j])
            print(S[:j]+q[idx+1])
            break
    else:
        print(-1)

alp=[chr(ord('a') + i) for i in range(26)]
unused=set(alp)
     
S=input()
#print("len",len(S))

if len(S)<26:
    for i in range(len(S)):
        if S[i] in unused:
            unused.remove(S[i])
    unused=sorted(unused)
    print(S+unused[0])
else:
    for j in range(len(S)-1,-1,-1):
        p=set(S[j:])
        #print(p)
        q=sorted(p)
        if S[j]==q[-1]:
            pass
        else:
            idx=q.index(S[j])
            print(S[:j]+q[idx+1])
            break
    else:
        print(-1)

Verdicts: Wrong Answer

Accepted