Red-Black Number (Codeforces 1593F)
Tags: Math, meet-in-the-middle

It is given a non-negative integer $$$x$$$, the decimal representation of which contains $$$n$$$ digits. You need to color each its digit in red or black, so that the number formed by the red digits is divisible by $$$A$$$, and the number formed by the black digits is divisible by $$$B$$$.At least one digit must be colored in each of two colors. Consider, the count of digits colored in red is $$$r$$$ and the count of digits colored in black is $$$b$$$. Among all possible colorings of the given number $$$x$$$, you need to output any such that the value of $$$|r - b|$$$ is the minimum possible.Note that the number $$$x$$$ and the numbers formed by digits of each color, may contain leading zeros.  Example of painting a number for $$$A = 3$$$ and $$$B = 13$$$ The figure above shows an example of painting the number $$$x = 02165$$$ of $$$n = 5$$$ digits for $$$A = 3$$$ and $$$B = 13$$$. The red digits form the number $$$015$$$, which is divisible by $$$3$$$, and the black ones — $$$26$$$, which is divisible by $$$13$$$. Note that the absolute value of the difference between the counts of red and black digits is $$$1$$$, it is impossible to achieve a smaller value.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then $$$t$$$ test cases follow.Each test case consists of two lines. The first line contains three integers $$$n$$$, $$$A$$$, $$$B$$$ ($$$2 \le n \le 40$$$, $$$1 \le A, B \le 40$$$). The second line contains a non-negative integer $$$x$$$ containing exactly $$$n$$$ digits and probably containing leading zeroes.

Output: For each test case, output in a separate line:  -1 if the desired coloring does not exist;  a string $$$s$$$ of $$$n$$$ characters, each of them is a letter 'R' or 'B'. If the $$$i$$$-th digit of the number $$$x$$$ is colored in red, then the $$$i$$$-th character of the string $$$s$$$ must be the letter 'R', otherwise the letter 'B'. The number formed by digits colored red should divisible by $$$A$$$. The number formed by digits colored black should divisible by $$$B$$$. The value $$$|r-b|$$$ should be minimal, where $$$r$$$ is the count of red digits, $$$b$$$ is the count of black digits. If there are many possible answers, print any of them.

Note: The first test case is considered in the statement.In the second test case, there are no even digits, so it is impossible to form a number from its digits that is divisible by $$$2$$$.In the third test case, each coloring containing at least one red and one black digit is possible, so you can color $$$4$$$ digits in red and $$$4$$$ in black ($$$|4 - 4| = 0$$$, it is impossible to improve the result).In the fourth test case, there is a single desired coloring.

Sample Inputs:
4
5 3 13
02165
4 2 1
1357
8 1 1
12345678
2 7 9
90

Sample Outputs:
RBRBR
-1
BBRRRRBB
BR

Solution (Python):
import sys
input = sys.stdin.readline

def f(x, y):
    return x * n + y

def g(x, y):
    return x * b + y

def h(x, y):
    return (x // n, x % n, y // b, y % b)
t = int(input())
dp = [[0] * 1600 for _ in range(42 * 42)]
for i in range(1, t + 1):
    (n, a, b) = map(int, input().split())
    x = list(input().rstrip())
    x.reverse()
    powa = [1 % a]
    for _ in range(n + 5):
        powa.append(10 * powa[-1] % a)
    powb = [1 % b]
    for _ in range(n + 5):
        powb.append(10 * powb[-1] % b)
    dp[0][0] = i
    for j in range(n):
        pa = powa[j]
        for k in range(n):
            if j + k >= n:
                break
            pb = powb[k]
            y = int(x[j + k])
            u = f(j, k)
            for l in range(a):
                for m in range(b):
                    v = g(l, m)
                    if not dp[u][v] == i:
                        continue
                    if j + 1 < n:
                        dp[f(j + 1, k)][g((l + y * pa) % a, m)] = i
                    if k + 1 < n:
                        dp[f(j, k + 1)][g(l, (m + y * pb) % b)] = i
    (u, v) = (-1, -1)
    for j in range(n // 2, 0, -1):
        k = n - j
        if dp[f(j, k)][0] == i:
            (u, v) = (f(j, k), 0)
            break
        if dp[f(k, j)][0] == i:
            (u, v) = (f(k, j), 0)
            break
    if u == v == -1:
        ans = -1
        print(ans)
        continue
    ans = []
    (j, k, l, m) = h(u, v)
    for c in range(n - 1, -1, -1):
        if j > 0 and dp[f(j - 1, k)][g((l - int(x[c]) * powa[j - 1]) % a, m)] == i:
            l = (l - int(x[c]) * powa[j - 1]) % a
            j -= 1
            ans.append('R')
        else:
            m = (m - int(x[c]) * powb[k - 1]) % b
            k -= 1
            ans.append('B')
        (u, v) = (f(j, k), f(l, m))
    print(''.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, A, B) = map(int, input().split())
    X = [int(x) for x in input().rstrip()]
    N = (n + 1) * (n + 1) * A * B

    def encode(i, r, a, b):
        v = i
        v = v * (n + 1) + r
        v = v * A + a
        v = v * B + b
        return v

    def nreds(v):
        v //= A * B
        return v % (n + 1)
    dp = [-1] * N
    dp[0] = 0
    for (i, d) in enumerate(X):
        for r in range(i + 1):
            for a in range(A):
                for b in range(B):
                    val = encode(i, r, a, b)
                    if dp[val] == -1:
                        continue
                    na = (a * 10 + d) % A
                    nval = encode(i + 1, r + 1, na, b)
                    dp[nval] = val
                    nb = (b * 10 + d) % B
                    nval = encode(i + 1, r, a, nb)
                    dp[nval] = val
    ans = n
    s = -1
    for r in range(1, n):
        val = encode(n, r, 0, 0)
        if dp[val] == -1:
            continue
        if abs(n - 2 * r) < ans:
            ans = abs(n - 2 * r)
            s = val
    if ans == n:
        print(-1)
        return
    res = ''
    for _ in range(n):
        ps = dp[s]
        if nreds(ps) == nreds(s):
            res += 'B'
        else:
            res += 'R'
        s = ps
    print(res[::-1])
    return
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
inf = 2147483647

def main(t):
    (n, a, b) = map(int, input().split())
    s = input()
    s = [int(s[i]) for i in range(n)]

    def getindex(index, pre, ma, mb):
        return index * (n + 1) * a * b + pre * a * b + ma * b + mb
    dp = [-1] * (a * b * (n + 1) * (n + 1))
    dp[0] = 0
    for index in range(n):
        for pre in range(index + 1):
            for ma in range(a):
                for mb in range(b):
                    num = getindex(index, pre, ma, mb)
                    if dp[num] < 0:
                        continue
                    nextnum1 = getindex(index + 1, pre + 1, (ma * 10 + s[index]) % a, mb)
                    nextnum2 = getindex(index + 1, pre, ma, (mb * 10 + s[index]) % b)
                    dp[nextnum1] = num
                    dp[nextnum2] = num
    for diff in range(n):
        if n + diff & 1:
            continue
        for curr in [(n + diff) // 2, (n - diff) // 2]:
            if dp[getindex(n, curr, 0, 0)] < 0:
                continue
            num = getindex(n, curr, 0, 0)
            ans = ''
            while num > 0:
                num = dp[num]
                pre = curr
                curr = num % ((n + 1) * a * b) // (a * b)
                if pre == curr:
                    ans += 'B'
                else:
                    ans += 'R'
            print(ans[::-1])
            return
    print(-1)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1