A16873. Ghostfires
编程题
普及+/提高
知识点
题目描述
OtterZ 决定用幽灵火制造一种武器。他收集了若干红色、绿色和蓝色的幽灵火。他将把一些幽灵火排成一行来制造武器。为了让武器更强大,OtterZ 会使用尽可能多的幽灵火。但是,如果有两个相同颜色的幽灵火相邻,或者在排成一行时中间隔着恰好两个幽灵火(即间隔 2 个位置)时再次出现相同颜色,武器将变得无法控制。
具体来说,OtterZ 收集了 $r$ 个红色幽灵火,$g$ 个绿色幽灵火,和 $b$ 个蓝色幽灵火。他希望构造一个只包含字符
- 字符串 $s$ 中
- 对于所有 $1 \le i \le |s|-1$,有 $s_i \ne s_{i+1}$。
- 对于所有 $1 \le i \le |s|-3$,有 $s_i \ne s_{i+3}$。
- $s$ 的长度应尽可能长。
请帮助 OtterZ 构造一个满足要求的排列。虽然可能存在多个可行方案,但只需输出任意一个即可。
具体来说,OtterZ 收集了 $r$ 个红色幽灵火,$g$ 个绿色幽灵火,和 $b$ 个蓝色幽灵火。他希望构造一个只包含字符
R、G、B 的字符串 $s$,满足下列条件:- 字符串 $s$ 中
R、G、B 的出现次数分别不超过 $r$、$g$、$b$。- 对于所有 $1 \le i \le |s|-1$,有 $s_i \ne s_{i+1}$。
- 对于所有 $1 \le i \le |s|-3$,有 $s_i \ne s_{i+3}$。
- $s$ 的长度应尽可能长。
请帮助 OtterZ 构造一个满足要求的排列。虽然可能存在多个可行方案,但只需输出任意一个即可。
输入格式
每个测试包含多组数据。第一行包含测试组数 $t$($1 \le t \le 10^4$)。
接下来的 $t$ 行,每行为一组测试数据,包含三个整数 $r$、$g$、$b$($0 \le r,g,b \le 10^6$,$r+g+b>0$),分别表示红色、绿色和蓝色幽灵火的数量。
保证所有测试数据中 $r+g+b$ 的总和不超过 $10^6$。
接下来的 $t$ 行,每行为一组测试数据,包含三个整数 $r$、$g$、$b$($0 \le r,g,b \le 10^6$,$r+g+b>0$),分别表示红色、绿色和蓝色幽灵火的数量。
保证所有测试数据中 $r+g+b$ 的总和不超过 $10^6$。
输出格式
对于每组查询,输出一个只包含字符
如果有多种答案,输出任意一个即可。
R、G、B 的字符串 $s$,其中 $s_i$ 为 R、G 或 B,表示第 $i$ 个幽灵火的颜色为红色、绿色或蓝色。如果有多种答案,输出任意一个即可。
输入输出样例
输入 #1
5 0 0 1 1 1 1 0 3 0 2 2 2 2 7 3
输出 #1
B RGB G GBRBRG GRGRGBGBGBG
说明/提示
对于第一个测试用例,
对于第二个测试用例,
对于第三个测试用例,
B 是唯一合法的构造方式。对于第二个测试用例,
RGB、RBG、GRB、BRG 和 BGR 都是正确答案。对于第三个测试用例,
GG 和 GGG 不合法,因为 $s_1 = s_2$。