HDU-5670 Machine

2016年04月28日 |

acm

| acm 水题

题目：

Machine Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 543 Accepted Submission(s): 313

Problem Description There is a machine with m(2≤m≤30) coloured bulbs and a button.When the button is pushed, the rightmost bulb changes. For any changed bulb,

if it is red now it will be green;

if it is green now it will be blue;

if it is blue now it will be red and the bulb that on the left(if it exists) will change too.

Initally all the bulbs are red. What colour are the bulbs after the button be pushed n(1≤n<263) times?

Input There are multiple test cases. The first line of input contains an integer T(1≤T≤15) indicating the number of test cases. For each test case:

The only line contains two integers m(2≤m≤30) and n(1≤n<263).

Output For each test case, output the colour of m bulbs from left to right. R indicates red. G indicates green. B indicates blue.

Sample Input

2 3 1 2 3

Sample Output

RRG GR

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>

using namespace std;

inline char out(unsigned long long a)
{
    switch (a%3)
    {
    case 0:
        return 'R';
    case 1:
        return 'G';
    case 2:
        return 'B';
    }
}

unsigned long long mypow(unsigned int a, unsigned int b)
{
    unsigned long long r = 1;
    while (b--)
    {
        r *= a;
    }
    return r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--)
    {
        unsigned long long n;
        unsigned int m;
        cin >> m >> n;

        for (unsigned int i = 1;i <= m;++i)
        {
            unsigned long long r = mypow(3, m - i);
            cout << out(n / r);
        }
        cout << endl;
    }
}

解析&吐槽：

一道水题。注意最右边的灯泡是按一下按钮改变一次，从右边数第二个灯泡是按 3 下按钮改变一次，第三个是 9 下按钮。因此第 n 个就是按 3^(n-1)个按钮改变一次了。 本题的幂运算需要自己写函数，cmath 自带的 pow 没法返回 long long，会因精度损失而导致 wa。