有一个机器,它有 m (2\leq m\leq 30)m(2≤m≤30) 个彩灯和一个按钮。每按下按钮时,最右边的彩灯会发生一次变换。变换为: 1. 如果当前状态为红色,它将变成绿色; 2.如果当前状态为绿色,它将变成蓝色; 3.如果当前状态为蓝色,它将变成红色,并且它左边的彩灯(如果存在)也会发生一次变换。 初始状态下所有的灯都是红色的。
询问按下按钮 n (1\leq n< {2}^{63})n(1≤n<263) 次以后各个彩灯的颜色。
输入描述
输入包含多组数据. 第一行有一个整数T (1\leq T\leq 15)T(1≤T≤15), 表示测试数据的组数. 对于每组数据:
唯一的一行包含2个整数 m (2\leq m\leq 30)m(2≤m≤30) 和 n (1\leq n< {2}^{63})n(1≤n<263) 。
输出描述
对于每组数据,输出一个长度为mm的字符串,表示从左到右mm个彩灯的颜色。
R代表红色;G代表绿色;B代表蓝色。
输入样例
2
3 1
2 3
输出样例
RRG
GR
红、绿、蓝分别表示0、1、2,每次操作就相当于+1,原问题就转化为求n的三进制
表示的最低的m位,即求 n mod 3^m3的三进制表示。
复杂度 O(m)O(m)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
int main()
{
int m ,t;
LL n;
scanf("%d", &t);
int color[];
while (t--)
{
memset(color, , sizeof(color));
scanf("%d%I64d", &m, &n);
int cnt = m;
while (n > && m > )
{
color[m--] = n % ;
n = n / ;
}
for (int i = ; i <= cnt; i++)
{
if (color[i] == )
printf("R");
else if(color[i] == )
printf("G");
else if (color[i] == )
printf("B");
}
printf("\n");
}
return ;
}