Problem:


Score : 1100 points

Problem Statement

Let f(A, B), where A and B are positive integers, be the string satisfying the following conditions:

f(A, B) has length A + B;

f(A, B) contains exactly A letters A and exactly B letters B;

The length of the longest substring of f(A, B) consisting of equal letters (ex., AAAAA or BBBB) is as small as possible under the conditions above;

f(A, B) is the lexicographically smallest string satisfying the conditions above.

For example, f(2, 3) = BABAB, and f(6, 4) = AABAABAABB.

Answer Q queries: find the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Constraints

1 \leq Q \leq 10^3

1 \leq A_i, B_i \leq 5 \times 10^8

1 \leq C_i \leq D_i \leq A_i + B_i

D_i - C_i + 1 \leq 100

All input values are integers.

Partial Score

500 points will be awarded for passing the testset satisfying 1 \leq A_i, B_i \leq 10^3.

Input

Input is given from Standard Input in the following format:

Q
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_Q B_Q C_Q D_Q

Output

For each query i in order of input, print a line containing the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Sample Input 1

5
2 3 1 5
6 4 1 10
2 3 4 4
6 4 3 7
8 10 5 8

Sample Output 1

BABAB
AABAABAABB
A
BAABA
ABAB



Sample input:
5
2 3 1 5
6 4 1 10
2 3 4 4
6 4 3 7
8 10 5 8


Sample output:
BABAB
AABAABAABB
A
BAABA
ABAB

Submission status: Wrong Answer

Solution code:
Q=int(input())
for i in range(Q):
  a,b,c,d=map(int,input().split())
  if a<=b:
    if b%a==0:
      k=b//a
      s=("A"+k*"B")*a
      print(s[c-1:d])
    else:
      k=(a//b)+1
      s="B"*(b%a)+("A"+k*"B")*a
      print(s[c-1:d])
  else:
    if a%b==0:
      k=a//b
      s=("A"*k+"B")*b
      print(s[c-1:d])
    else:
      k=(a//b)+1
      s=("A"*k+"B")*b+"A"*(a%b)
      print(s[c-1:d])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8), cache=True)
def find_min_length(a, b):
    if a < b:
        a, b = b, a
    return (a + b) // (b + 1)

@njit((i8, i8, i8, i8), cache=True)
def f(a, b, c, d):
    L = find_min_length(a, b)
    ret = ''

    def test(a, b, L):
        # ...B の直後に A を a 個、B を b 個置けるかどうか
        ok = a >= 0 and b >= 0
        if a == 0:
            ok = ok and (b <= L - 1)
        else:
            ok = ok and (a <= L * (b + 1))
            ok = ok and (1 + b <= L * (a + 1))
        return ok

    def add(s, x, t, y, n):
        # 文字列に (s*x + t*y)*n を追加
        nonlocal c, d, ret
        if (x + y) * n < c:
            c -= (x + y) * n
            d -= (x + y) * n
            return
        m = (c - 1) // (x + y)
        c -= m * (x + y)
        d -= m * (x + y)
        n -= m
        while n and c <= d:
            if d <= x:
                ret += s * (d - c + 1)
                d = 0
                return
            if 1 <= c <= x:
                ret += s * (x - c + 1)
                c = x + 1
            ret += t * (min(d, x + y) - c + 1)
            c = 1
            d -= x + y
            n -= 1

    # AAABAAAB と n セット並べてしまって大丈夫かどうか
    l, r = 0, b + 100
    while l + 1 < r:
        m = (l + r) >> 1
        a1, b1 = a - L * m, b - m
        if test(a1, b1, L):
            l = m
        else:
            r = m
    n = l
    if n == 0:
        add('B', 1, 'A', 0, 1)
        b -= 1
    else:
        add('A', L, 'B', 1, n)
        a -= L * n
        b -= n
    # 次に、A^kB
    l, r = 0, L
    while l + 1 < r:
        m = (l + r) // 2
        if test(a - m, b - 1, L):
            l = m
        else:
            r = m
    k = l
    if k:
        add('A', k, 'B', 1, 1)
        a -= k
        b -= 1
    # 以降は、Aは高々ひとつずつ
    if not a:
        add('B', b, 'A', 0, 1)
        return ret

    # B^kA、kはなるべく少なく
    l, r = -1, L - 1
    while l + 1 < r:
        m = (l + r) // 2
        if test(a - 1, b - m, L):
            r = m
        else:
            l = m
    if k >= 0:
        add('B', k, 'A', 1, 1)
        a -= 1
        b -= k
    # B^LA をいくつか
    n = min(b // L, a)
    add('B', L, 'A', 1, n)
    a -= n
    b -= n * L
    add('B', b, 'A', 0, 1)
    return ret

ABCD = np.array(read().split(), np.int64)[1:]

for a, b, c, d in ABCD.reshape(-1, 4):
    print(f(a, b, c, d))

Submission status: Wrong Answer

Solution code:
T=int(input())
for TT in range(T):
	a,b,c,d=map(int,input().split(' '))
	l,x,y=(a+b)//(min(a,b)+1),0,0
	if a*l<=b:
		y=a+b
	elif b*l<=a:
		x=a+b
	else:
		x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	out=""
	for i in range(c,d+1):
		if i<=x:
			out+="AB"[i%(l+1)==0]
		elif a+b-i-1<=y:
			out+="BA"[(a+b-i+1)%(l+1)==0]
		else:
			out+="AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(out)

Submission status: Wrong Answer

Solution code:
T=int(input())
for TT in range(T):
	a,b,c,d=map(int,input().split(' '))
	l,x,y=(a+b)//(min(a,b)+1),0,0
	if a*l<=b:
		y=a+b
	elif b*l<=a:
		x=a+b
	else:
		x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	out=""
	for i in range(c,d+1):
		if i<=x:
			out+="AB"[i%(l+1)==0]
		elif a+b-i-1<=y:
			out+="BA"[(a+b-i+1)%(l+1)==0]
		else:
			out+="AB"[a-x+x/(l+1)-y/(l+1)==0]
	print(out)

Submission status: Wrong Answer

Solution code:
Q = int(input())

def oldChain(index, blockLength):
    if index%blockLength==0:
        return "B"
    else:
        return "A"

def newChain(index, blockLength):
    if index%blockLength==0:
        return "A"
    else:
        return "B"

def residueChain(index, residueAyy):
    if index>residueAyy:
        return "B"
    else:
        return "A"

for i in range(Q):
    line = [int(i) for i in input().split()]
    A = line[0]
    B = line[1]
    C = line[2]
    D = line[3]
    maxLength = int((max(A, B)-1)/(min(A, B)+1))+1
    equalisers = A+B
    residueDifference = A-B
    if maxLength!=1:
        residueDifference = abs(A-B)%(maxLength - 1)
        residueDifference *= (A>B)-(A<B)
        equalisers = int(abs(A-B)/(maxLength-1))*(maxLength+1)
    neutral = int((A+B-equalisers)/(2*maxLength+2))
    residue = (A+B-equalisers)%(2*maxLength+2)
    neutral -= (residue == 0)
    residue += (residue == 0) * (2 * maxLength + 2)
    intersectionStart = (neutral*(maxLength+1)+equalisers)*(A>=B)+(A+B-equalisers-neutral*(maxLength+1)-residue)*(A<B)
    if residue>maxLength+1:
        if residueDifference>=0:
            intersectionStart += (maxLength + 1)
            residueDifference -= (maxLength - 1)
        else:
            residueDifference += (maxLength - 1)
        residue -= (maxLength + 1)
    residueAyy = int((residue+residueDifference)/2)
    ans = [0 for i in range(D-C+1)]
    for i in range(C,D+1):
        if i<intersectionStart+1:
            ans[i-C]=oldChain(i,maxLength+1)
        elif i>intersectionStart+residue:
            ans[i-C]=newChain(A+B-i+1,maxLength+1)
        else:
            ans[i-C]=residueChain(i-intersectionStart,residueAyy)
    print("".join(ans)+"\n")

Submission status: Wrong Answer

Solution code:
Q = int(input())

def oldChain(index, blockLength):
    if index%blockLength==0:
        return "B"
    else:
        return "A"

def newChain(index, blockLength):
    if index%blockLength==0:
        return "A"
    else:
        return "B"

def residueChain(index, residueAyy):
    if index>residueAyy:
        return "B"
    else:
        return "A"

for i in range(Q):
    line = [int(i) for i in input().split()]
    A = line[0]
    B = line[1]
    C = line[2]
    D = line[3]
    maxLength = int((max(A, B)-1)/(min(A, B)+1))+1
    equalisers = A+B
    residueDifference = A-B
    if maxLength!=1:
        residueDifference = abs(A-B)%(maxLength - 1)
        residueDifference *= (A>B)-(A<B)
        equalisers = int(abs(A-B)/(maxLength-1))*(maxLength+1)
    neutral = int((A+B-equalisers)/(2*maxLength+2))
    residue = (A+B-equalisers)%(2*maxLength+2)
    intersectionStart = (neutral*(maxLength+1)+equalisers)*(A>=B)+(A+B-equalisers-neutral*(maxLength+1)-residue)*(A<B)
    if residue>maxLength+1:
        if residueDifference>=0:
            intersectionStart += (maxLength + 1)
            residueDifference -= (maxLength - 1)
        else:
            residueDifference += (maxLength - 1)
        residue -= (maxLength + 1)
    residueAyy = int((residue+residueDifference)/2)
    ans = [0 for i in range(D-C+1)]
    for i in range(C,D+1):
        if i<intersectionStart+1:
            ans[i-C]=oldChain(i,maxLength+1)
        elif i>intersectionStart+residue:
            ans[i-C]=newChain(A+B-i+1,maxLength+1)
        else:
            ans[i-C]=residueChain(i-intersectionStart,residueAyy)
    print("".join(ans)+"\n")

Submission status: Wrong Answer

Solution code:
Q = int(input())

def oldChain(index, blockLength):
    if index%blockLength==0:
        return "B"
    else:
        return "A"

def newChain(index, blockLength):
    if index%blockLength==0:
        return "A"
    else:
        return "B"

def residueChain(index, residueAyy):
    if index>residueAyy:
        return "B"
    else:
        return "A"

for i in range(Q):
    line = [int(i) for i in input().split()]
    A = line[0]
    B = line[1]
    C = line[2]
    D = line[3]
    maxLength = int((max(A, B)-1)/(min(A, B)+1))+1
    equalisers = A+B
    residueDifference = A-B
    if maxLength!=1:
        residueDifference = abs(A-B)%(maxLength - 1)
        residueDifference *= (A>B)-(A<B)
        equalisers = int(abs(A-B)/(maxLength-1))*(maxLength+1)
    neutral = int((A+B-equalisers)/(2*maxLength+2))
    residue = (A+B-equalisers)%(2*maxLength+2)
    print(-34%6)
    intersectionStart = (neutral*(maxLength+1)+equalisers)*(A>=B)+(A+B-equalisers-neutral*(maxLength+1)-residue)*(A<B)
    if residue>maxLength+1:
        if residueDifference>=0:
            intersectionStart += (maxLength + 1)
            residueDifference -= (maxLength - 1)
        else:
            residueDifference += (maxLength - 1)
        residue -= (maxLength + 1)
    residueAyy = int((residue+residueDifference)/2)
    ans = [0 for i in range(D-C+1)]
    for i in range(C,D+1):
        if i<intersectionStart+1:
            ans[i-C]=oldChain(i,maxLength+1)
        elif i>intersectionStart+residue:
            ans[i-C]=newChain(A+B-i+1,maxLength+1)
        else:
            ans[i-C]=residueChain(i-intersectionStart,residueAyy)
    print("".join(ans)+"\n")

Submission status: Wrong Answer

Solution code:
Q = int(input())

def oldChain(index, blockLength):
    if index%blockLength==0:
        return "B"
    else:
        return "A"

def newChain(index, blockLength):
    if index%blockLength==0:
        return "A"
    else:
        return "B"

def residueChain(index, residueAyy):
    if index>residueAyy:
        return "B"
    else:
        return "A"

for i in range(Q):
    line = [int(i) for i in input().split()]
    A = line[0]
    B = line[1]
    C = line[2]
    D = line[3]
    maxLength = int((max(A, B)-1)/(min(A, B)+1))+1
    equalisers = A+B
    residueDifference = A-B
    if maxLength!=1:
        residueDifference %= (maxLength - 1)
        residueDifference *= (A>B)-(A<B)
        equalisers = int(abs(A-B)/(maxLength-1))*(maxLength+1)
    neutral = int((A+B-equalisers)/(2*maxLength+2))
    residue = (A+B-equalisers)%(2*maxLength+2)
    intersectionStart = (neutral*(maxLength+1)+equalisers)*(A>=B)+(A+B-equalisers-neutral*(maxLength+1)-residue)*(A<B)
    if residue>maxLength+1:
        if residueDifference>=0:
            intersectionStart += (maxLength + 1)
            residueDifference -= (maxLength - 1)
        else:
            residueDifference += (maxLength - 1)
        residue -= (maxLength + 1)
    residueAyy = int((residue+residueDifference)/2)
    ans = [0 for i in range(D-C+1)]
    for i in range(C,D+1):
        if i<intersectionStart+1:
            ans[i-C]=oldChain(i,maxLength+1)
        elif i>intersectionStart+residue:
            ans[i-C]=newChain(A+B-i+1,maxLength+1)
        else:
            ans[i-C]=residueChain(i-intersectionStart,residueAyy)
    print("".join(ans))

Submission status: Wrong Answer

Solution code:
Q = int(input())

def oldChain(index, blockLength):
    if index%blockLength==0:
        return "B"
    else:
        return "A"

def newChain(index, blockLength):
    if index%blockLength==0:
        return "A"
    else:
        return "B"

def residueChain(index, residueAyy):
    if index>residueAyy:
        return "B"
    else:
        return "A"

for i in range(Q):
    line = [int(i) for i in input().split()]
    A = line[0]
    B = line[1]
    C = line[2]
    D = line[3]
    maxLength = int((max(A, B)-1)/(min(A, B)+1))+1
    equalisers = A+B
    residueDifference = A-B
    if maxLength!=1:
        residueDifference %= (maxLength - 1)
        equalisers = int(abs(A-B)/(maxLength-1))*(maxLength+1)
    neutral = int((A+B-equalisers)/(2*maxLength+2))
    residue = (A+B-equalisers)%(2*maxLength+2)
    intersectionStart = (neutral*(maxLength+1)+equalisers)*(A>=B)+(A+B-equalisers-neutral*(maxLength+1)-residue)*(A<B)
    if residue>maxLength+1:
        if residueDifference>=0:
            intersectionStart += (maxLength + 1)
            residueDifference -= (maxLength - 1)
        else:
            residueDifference += (maxLength - 1)
        residue -= (maxLength + 1)
    residueAyy = int((residue+residueDifference)/2)
    ans = [0 for i in range(D-C+1)]
    for i in range(C,D+1):
        if i<intersectionStart+1:
            ans[i-C]=oldChain(i,maxLength+1)
        elif i>intersectionStart+residue:
            ans[i-C]=newChain(A+B-i+1,maxLength+1)
        else:
            ans[i-C]=residueChain(i-intersectionStart,residueAyy)
    print("".join(ans))

Submission status: Wrong Answer

Solution code:
Q = int(input())

def oldChain(index, blockLength):
    if index%blockLength==0:
        return "B"
    else:
        return "A"

def newChain(index, blockLength):
    if index%blockLength==0:
        return "A"
    else:
        return "B"

def residueChain(index, residueAyy):
    if index>residueAyy:
        return "B"
    else:
        return "A"

for i in range(Q):
    line = [int(i) for i in input().split()]
    A = line[0]
    B = line[1]
    C = line[2]
    D = line[3]
    maxLength = int((max(A, B)-1)/(min(A, B)+1))+1
    equalisers = A+B
    residueDifference = A-B
    if maxLength!=1:
        residueDifference %= (maxLength - 1)
        equalisers = int(abs(A-B)/(maxLength-1))*(maxLength+1)
    neutral = int((A+B-equalisers)/(2*maxLength+2))
    residue = (A+B-equalisers)%(2*maxLength+2)
    intersectionStart = neutral*(maxLength+1)+equalisers*(A>B)
    if residue>maxLength+1:
        if residueDifference>=0:
            intersectionStart += (maxLength + 1)
            residueDifference -= (maxLength - 1)
        else:
            residueDifference += (maxLength - 1)
        residue -= (maxLength + 1)
    residueAyy = int((residue+residueDifference)/2)
    ans = [0 for i in range(D-C+1)]
    for i in range(C,D+1):
        if i<intersectionStart+1:
            ans[i-C]=oldChain(i,maxLength+1)
        elif i>intersectionStart+residue:
            ans[i-C]=newChain(A+B-i+1,maxLength+1)
        else:
            ans[i-C]=residueChain(i-intersectionStart,residueAyy)
    print("".join(ans))

Submission status: Wrong Answer

Solution code:
def binary_search(a,b):
	"""str_Aで文字Aを使う回数を探索する"""
	l = 0
	r = a
	retval = (-1)
	while l <= r:
		mid = (l+r) // 2
		if mid % n == 0:
			used_b = (mid // n) -1
		else:
			used_b = mid // n 
		if (b - used_b) <= ((a-mid) * n):
			l = mid + 1
		else:
			r = mid - 1
			if (b - used_b) <= ((a-mid+1) * n):
				retval = max(mid,retval)

	return max(retval,mid)
  
Q = int(input())
for i in range(Q):
	a,b,c,d = map(int,input().split(" "))
	max_ab = max(a,b)
	min_ab = min(a,b)
	if max_ab % (min_ab+1) == 0:
		n = max_ab // (min_ab+1)
	else:
		n = ( max_ab // (min_ab+1)) + 1	
	a_count = a
	b_count = b - n
	A_str = ""
	B_str = ('B'* n)
	while a_count > 0:
		A_str += ('A' * n) 
		A_str += 'B'
		a_count -= n
	while b_count > 0:
		B_str += 'A'
		B_str += ('B'* n)
		b_count -= n
	N_a = binary_search(a,b)
	if (N_a) % n == 0 and N_a != 0:
		A_l = (N_a + (N_a // n) - 1)
	else:
		A_l = (N_a + (N_a // n))
	len_B = len(B_str)
	B_l = a + b - A_l
	ans = A_str[0:A_l] + B_str[len_B-B_l:len_B]
	#print(ans)
	print(ans[c-1:d])

Submission status: Wrong Answer

Solution code:
def binary_search(a,b):
	"""str_Aで文字Aを使う回数を探索する"""
	l = 0
	r = a
	retval = (-1)
	while l <= r:
		mid = (l+r) // 2
		if mid % n == 0:
			used_b = (mid // n) -1
		else:
			used_b = mid // n 

		if (b - used_b) <= ((a-mid) * n):

			l = mid + 1

		else:
			r = mid - 1
			if (b - used_b) < ((a-mid+1) * n):
				retval = max(mid,retval)

	return max(retval,mid)


Q = int(input())
for i in range(Q):
	a,b,c,d = map(int,input().split(" "))
	max_ab = max(a,b)
	min_ab = min(a,b)

	if max_ab % (min_ab+1) == 0:
		n = max_ab // (min_ab+1)
	else:
		n = ( max_ab // (min_ab+1)) + 1
	
	a_count = a
	b_count = b - n
	A_str = ""
	B_str = ('B'* n)
	while a_count > 0:
		A_str += ('A' * n) 
		A_str += 'B'
		a_count -= n

	while b_count > 0:
		B_str += 'A'
		B_str += ('B'* n)
		b_count -= n

	N_a = binary_search(a,b)
	if (N_a) % n == 0 and N_a != 0:
		A_l = (N_a + (N_a // n) - 1)
	else:
		A_l = (N_a + (N_a // n))

	B_l = a + b - A_l
	ans = A_str[0:A_l] + B_str[0:B_l]
	print(ans[c-1:d])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import bisect
Q = int(input())
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    xs = ((A - i + 1) * K < B - max(0, (i - 1) // K) for i in range(A + 1))
    p = bisect.bisect(list(xs), False)
    f = ''
    for i in range(C - 1, D):
        na = p
        nb = max(0, (na - 1) // K)
        if i < nb * (K + 1):
            f += ('A', 'B')[i % (K + 1) == K]
        elif i < na + nb:
            f += 'A'
        else:
            j = A + B - i - 1
            nb = B - nb
            na = max(0, (nb - 1) // K)
            if j < na * (K + 1):
                f += ('B', 'A')[j % (K + 1) == K]
            else:
                f += 'B'
    print(f)

Submission status: Wrong Answer

Solution code:
from math import ceil


def solve(a, b, c, d):
    l_max = int(ceil(max(a, b) / (min(a, b) + 1)))
    # lB-A = (l^2-1)r2 + l^2 - m
    tmp = l_max * b - a - l_max ** 2
    div = l_max ** 2 - 1
    if not div:
        # AB交互
        if b > a:
            c += 1
            d += 1
        e = d - c + 1
        base = 'AB' if c & 1 else 'BA'
        ans = base * (e // 2)
        if e & 1:
            ans += base[0]
        return ans
    r2 = ceil(tmp / (l_max ** 2 - 1))
    m = r2 * (l_max ** 2 - 1) - tmp
    r1 = b - l_max * (r2 + 1)
    border = (l_max + 1) * r1 + m
    if d <= border:
        sr, sp = divmod(c - 1, l_max + 1)
        er, ep = divmod(d, l_max + 1)
        base = 'A' * l_max + 'B'
        btwn = max(0, er - sr - 1)
        ans = base[sp:] + base * btwn + base[:ep]
        if m == 0:
            if d == border:
                if len(ans) > 1:
                    ans = ans[:-2] + 'BA'
                else:
                    ans = 'A'
            elif d == border - 1:
                ans = ans[:-1] + 'B'
        return ans
    elif c > border:
        c -= border
        d -= border
        sr, sp = divmod(c - 1, l_max + 1)
        er, ep = divmod(d, l_max + 1)
        base = 'B' * l_max + 'A'
        btwn = max(0, er - sr - 1)
        return base[sp:] + base * btwn + base[:ep]
    d -= border
    sr, sp = divmod(c - 1, l_max + 1)
    er, ep = divmod(d, l_max + 1)
    base1 = 'A' * l_max + 'B'
    base2 = 'B' * l_max + 'A'
    ans = base1[sp:] + base1 * (r1 - sr - 1) + 'A' * m + base2 * er + base2[:ep]
    if m == 0:
        if c == border:
            ans = 'A' + ans[1:]
        else:
            ans = ans[:border - c - 1] + 'BA' + ans[border - c + 1:]
    return ans


q = int(input())
buf = [solve(*map(int, input().split())) for _ in range(q)]
print('\n'.join(buf))

Submission status: Wrong Answer

Solution code:
from math import ceil


def solve(a, b, c, d):
    l_max = int(ceil(max(a, b) / (min(a, b) + 1)))
    # lB-A = (l^2-1)r2 + l^2 - m
    tmp = l_max * b - a - l_max ** 2
    div = l_max ** 2 - 1
    if not div:
        # AB交互
        if b > a:
            c += 1
            d += 1
        e = d - c + 1
        base = 'AB' if c & 1 else 'BA'
        ans = base * (e // 2)
        if e & 1:
            ans += base[0]
        return ans
    r2 = ceil(tmp / (l_max ** 2 - 1))
    m = r2 * (l_max ** 2 - 1) - tmp
    r1 = b - l_max * (r2 + 1)
    border = (l_max + 1) * r1 + m
    if d <= border:
        sr, sp = divmod(c - 1, l_max + 1)
        er, ep = divmod(d, l_max + 1)
        base = 'A' * l_max + 'B'
        btwn = max(0, er - sr - 1)
        return base[sp:] + base * btwn + base[:ep]
    elif c > border:
        c -= border
        d -= border
        sr, sp = divmod(c - 1, l_max + 1)
        er, ep = divmod(d, l_max + 1)
        base = 'B' * l_max + 'A'
        btwn = max(0, er - sr - 1)
        return base[sp:] + base * btwn + base[:ep]
    d -= border
    sr, sp = divmod(c - 1, l_max + 1)
    er, ep = divmod(d, l_max + 1)
    base1 = 'A' * l_max + 'B'
    base2 = 'B' * l_max + 'A'
    return base1[sp:] + base1 * (r1 - sr - 1) + 'A' * m + base2 * er + base2[:ep]


q = int(input())
buf = [solve(*map(int, input().split())) for _ in range(q)]
print('\n'.join(buf))

Submission status: Wrong Answer

Solution code:
from math import ceil


def solve(a, b, c, d):
    if a == b:
        s = 'AB' * a
        return s[c - 1:d]
    if a > b:
        long_len = int(ceil(a / (b + 1)))
        long_cnt_a = a // long_len
        remain_a = a - long_cnt_a * long_len
        if remain_a == 0:
            long_cnt_a -= 1
            remain_a = long_len
        if long_cnt_a == b:
            # AAABAAABAAABAA
            sr, sp = divmod(c - 1, (long_len + 1))
            er, ep = divmod(d, (long_len + 1))
            base = 'A' * long_len + 'B'
            btwn = max(0, er - sr - 1)
            return base[sp:] + base * btwn + base[:ep]
        # A: (long) (long) ... (long) (remain)
        # B: 1 1 1 ... (remain) (long) ... (long)
        long_cnt_b, remain_b = divmod(b - (long_cnt_a + 1), (long_len - 1))
        remain_b += 1
        b_cnt_1 = b - long_len * long_cnt_b - remain_b
        aa = [long_len] * long_cnt_a + [remain_a]
        bb = [1] * b_cnt_1 + [remain_b] + [long_len] * long_cnt_b
        s = ''
        for al, bl in zip(aa, bb):
            s += 'A' * al + 'B' * bl
        return s[c - 1:d]
    long_len = int(ceil(b / (a + 1)))
    long_cnt_b = b // long_len
    remain_b = b - long_cnt_b * long_len
    if remain_b == 0:
        long_cnt_b -= 1
        remain_b = long_len
    if long_cnt_b == a:
        s = 'B' * remain_b + ('A' + 'B' * long_len) * long_cnt_b
    else:
        long_cnt_a, remain_a = divmod(a - (long_cnt_b + 1), (long_len - 1))
        remain_a += 1
        a_cnt_1 = a - long_len * long_cnt_a - remain_a
        aa = [long_len] * long_cnt_a + [remain_a] + [1] * a_cnt_1
        bb = [remain_b] + [long_len] * long_cnt_b
        s = ''.join('A' * al + 'B' * bl for al, bl in zip(aa, bb))
    return s[c - 1:d]


q = int(input())
buf = [solve(*map(int, input().split())) for _ in range(q)]
print('\n'.join(buf))

Submission status: Wrong Answer

Solution code:
from math import ceil


def solve(a, b, c, d):
    if a == b:
        s = 'AB' * a
        return s[c:d + 1]
    if a > b:
        long_len = int(ceil(a / (b + 1)))
        long_cnt_a = a // long_len
        remain_a = a - long_cnt_a * long_len
        if remain_a == 0:
            long_cnt_a -= 1
            remain_a = long_len
        if long_cnt_a == b:
            # AAABAAABAAABAA
            sr, sp = divmod(c - 1, (long_len + 1))
            er, ep = divmod(d, (long_len + 1))
            base = 'A' * long_len + 'B'
            btwn = max(0, er - sr - 1)
            return base[sp:] + base * btwn + base[:ep]
        # A: (long) (long) ... (long) (remain)
        # B: 1 1 1 ... (remain) (long) ... (long)
        long_cnt_b, remain_b = divmod(b - (long_cnt_a + 1), (long_len - 1))
        remain_b += 1
        b_cnt_1 = b - long_len * long_cnt_b - remain_b
        aa = [long_len] * long_cnt_a + [remain_a]
        bb = [1] * b_cnt_1 + [remain_b] + [long_len] * long_cnt_b
        s = ''
        for al, bl in zip(aa, bb):
            s += 'A' * al + 'B' * bl
        return s[c:d + 1]
    long_len = int(ceil(b / (a + 1)))
    long_cnt_b = b // long_len
    remain_b = b - long_cnt_b * long_len
    if remain_b == 0:
        long_cnt_b -= 1
        remain_b = long_len
    if long_cnt_b == a:
        s = 'B' * remain_b + ('A' + 'B' * long_len) * long_cnt_b
        return s[c:d + 1]
    long_cnt_a, remain_a = divmod(a - (long_cnt_b + 1), (long_len - 1))
    remain_a += 1
    a_cnt_1 = a - long_len * long_cnt_a - remain_a
    aa = [1] * a_cnt_1 + [remain_a] + [long_len] * long_cnt_a
    bb = [long_len] * long_cnt_b + [remain_b]
    s = ''.join('A' * al + 'B' * bl for al, bl in zip(aa, bb))
    return s[c:d + 1]


q = int(input())
buf = [solve(*map(int, input().split())) for _ in range(q)]
print('\n'.join(buf))

Submission status: Wrong Answer

Solution code:
Q = int(input())
ans = []
for i in range(Q):
	a,b,c,d = map(int,input().split(" "))
	if a >= b:
		if (a % (b+1)) == 0:
			n = a // (b+1)
		else:
			n = (a // (b+1)) + 1

		times = a // n
		a_remain = a - times * n
		b_remain = b - times
		ans_str = ""
		for i in range(times):
			ans_str += (('A') * n)
			ans_str += 'B'

		ans_str += (('A') * (a_remain))
		ans_str += (('B') * (b_remain))

	else:
		if (b % (a+1)) == 0:
			n = b // (a+1)
		else:
			n = (b // (a+1)) + 1

		times = b // n
		b_remain = b - times * n
		a_remain = a - times
		if a_remain < 0:
			times -= 1
			b_remain += n

		ans_str = ""
		for i in range(times):
			ans_str += (('B') * n)
			ans_str += "A"

		ans_str += (('B') * (b_remain))
		ans_str += (('A') * (a_remain))
		ans_str = ans_str[::-1]

	ans.append(ans_str[c-1:d])

for i in ans:
	print(i)

Submission status: Wrong Answer

Solution code:
import itertools

def f(A,B):
  ans = ""
  ansl = 99999
  for s in itertools.permutations(["A"]*A+["B"]*B):
    s = "".join(s)
    l = 0
    p = -1
    for i in range(A+B):
      if i==A+B-1 or s[i]!=s[i+1]:
        l = max(l, i-p)
        p = i
    if l==ansl:
      ans = min(ans, s)
    elif l<ansl:
      ans = s
      ansl = l
  return ans

def f2(A,B):
  for l in range(A+B):
    ans = "Z"
    # ababa
    for an in range(1,A+1):
      for bn in range(an-1,an+2):
        if 0<bn<=B and an*l>=A and bn*l>=B:
          a = [1]*an
          t = A-an
          for i in range(an):
            x = min(t, l-1)
            a[i] += x
            t -= x
          b = [1]*bn
          t = B-bn
          for i in range(bn)[::-1]:
            x = min(t, l-1)
            b[i] += x
            t -= x
          s = ""
          if bn>an:
            s += "B"*b[0]
            b = b[1:]
          while a!=[]:
            s += "A"*a[0]
            a = a[1:]
            if b!=[]:
              s += "B"*b[0]
              b = b[1:]
          ans = min(ans, s)
    if ans!="Z":
      return ans

#print f(6,4)
# AABAABAABB
#print f2(6,4)

def hoge(s):
  l = 0
  an = 0
  bn = 0
  p = -1
  for i in range(A+B):
    if i==A+B-1 or s[i]!=s[i+1]:
      l = max(l, i-p)
      p = i
      if s[i]=="A":
        an += 1
      else:
        bn += 1
  return "%2d %2d,"%(l,an-bn)

"""
for A in range(1,17):
  for B in range(1,17):
    print hoge(f3(A,B)),
  print
"""

Q = input()
for _ in range(Q):
  A,B,C,D = map(int, raw_input().split())
  if A<1000 and B<1000:
    print f2(A,B)[C-1:D]
  else:
    print "-"

Submission status: Time Limit Exceeded

Solution code:
import sys,os,random
def f(A,B,p):
	if p and A>B:A,B=B,A
	return(B+A)//(A+1)
Q=int(input())
while Q:
	Q-=1
	A,B,C,D=map(int,input().split())
	o=f(A,B,1)
	res=""
	while A>0 or B>0:
		for i in range(o,0,-1):
			if A>=i and f(A-i,B,0)<=o:
				res+="A"*i
				A-=i
				break
		for i in range(1,o+1):
			if B>=i and f(B-i,A,0)<=o:
				res+="B"*i
				B-=i
				break
	print(res[C-1:D])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
import bisect
Q = int(input())
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    xs = ((A - i + 1) * K < B - max(0, (i - 1) // K) for i in range(A + 1))
    p = bisect.bisect(list(xs), False)
    f = ''
    for i in range(C - 1, D):
        na = p - 1
        nb = max(0, (na - 1) // K)
        if i < nb * (K + 1):
            f += ('A', 'B')[i % (K + 1) == K]
        elif i < na + nb:
            f += 'A'
        else:
            j = A + B - i - 1
            nb = B - nb
            na = max(0, (nb - 1) // K)
            if j < na * (K + 1):
                f += ('B', 'A')[j % (K + 1) == K]
            else:
                f += 'B'
    print(f)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
Q = int(input())
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    f = ''
    ca, cb = 0, 0
    while A + B > 0:
        if B <= A * K:
            if A > 0 and ca < K:
                A -= 1
                ca += 1
                cb = 0
                f += 'A'
            elif B > 0:
                B -= 1
                ca = 0
                cb += 1
                f += 'B'
        else:
            if B > 0 and cb < K:
                B -= 1
                ca = 0
                cb += 1
                f += 'B'
            elif A > 0:
                A -= 1
                ca += 1
                cb = 0
                f += 'A'
    print(f[C - 1:D])