← 返回题目列表

Codeforces · 1593/F

F. 红黑号码

中文机器翻译题面 查看原题

给出一个非负整数$$$x$$$,其十进制表示包含$$$n$$$位。您需要将其每个数字涂成红色或黑色,以便红色数字形成的数字可以被 $$$A$$$ 整除,黑色数字形成的数字可以被 $$$B$$$ 整除。

两种颜色中的每一种都必须至少有一个数字。考虑一下,红色的数字个数是$$$r$$$,黑色的数字个数是$$$b$$$。在给定数字 $$$x$$$ 的所有可能颜色中,您需要输出任何使得 $$$|r - b|$$$ 的值尽可能小的值。

请注意,数字 $$$x$$$ 以及由每种颜色的数字组成的数字可能包含前导零。

为 $$$A = 3$$$ 和 $$$B = 13$$$ 绘制数字的示例

上图显示了为 $$$A = 3$$$ 和 $$$B = 13$$$ 绘制 $$$n = 5$$$ 位数字 $$$x = 02165$$$ 的示例。红色数字构成数字 $$$015$$$,可被 $$$3$$$ 整除,黑色数字构成数字 $$$26$$$,可被 $$$13$$$ 整除。注意,红色和黑色数字的计数之差的绝对值为$$$1$$$,不可能达到更小的值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例由两行组成。第一行包含三个整数 $$$n$$$、$$$A$$$、$$$B$$$ ($$$2 \le n \le 40$$$、$$$1 \le A、B \le 40$$$)。第二行包含一个非负整数 $$$x$$$,恰好包含 $$$n$$$ 数字,并且可能包含前导零。

输出

对于每个测试用例,在单独的行中输出:

- 如果所需的颜色不存在,则为 -1;
- 一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$,每个字符都是字母“R”或“B”。如果数字 $$$x$$$ 的第 $$$i$$$ 位为红色,则字符串 $$$s$$$ 的第 $$$i$$$ 个字符必须是字母“R”,否则为字母“B”。

由红色数字组成的数字应能被 $$$A$$$ 整除。由黑色数字组成的数字应能被 $$$B$$$ 整除。 $$$|r-b|$$$ 值应该是最小的,其中 $$$r$$$ 是红色数字的计数,$$$b$$$ 是黑色数字的计数。如果有很多可能的答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

RBRBR
-1
BBRRRRBB
BR

注意

声明中考虑第一个测试用例。

在第二个测试用例中,没有偶数位,因此不可能从其数字中形成可被 $$$2$$$ 整除的数字。

在第三个测试用例中,每种着色至少包含一个红色和一个黑色数字是可能的,因此您可以将 $$$4$$$ 数字着色为红色,将 $$$4$$$ 着色为黑色($$$|4 - 4| = 0$$$,无法改善结果)。

在第四个测试用例中,有一种所需的颜色。