|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||4||4||3||100.000%|
We define a string as a sequence of characters ‘(‘ and ‘)’.
We define a well bracketed string as a string that can be transformed into a correct arithmetic expression by inserting characters ‘1’ and ‘+’ between the characters of the string. For example, strings "()()" and "(())” are correct and their possible expressions are "(1)+(1)" and "((1+1)+1)" respectively, whilst ")(" and "(" are not. The empty string is defined as well bracketed.
Bogdan Shepherd and Rolling Costel work in the B.U.A.P. (Bureau of Unnecessary Algorithmic Problems), useless brackets division. They usually receive two types of tasks:
Bogdan and Costel usually solve the two questions using C / C++, but the Grandpa of Evil hacked their computers and they can only use Rust. Unfortunately they don’t know anything about Rust; can you help them? Of course, you do not have such limitations, so you can use any language you want (i.e. C / C++ / Pascal).
The first line contains an integer P, denoting the type of problem you will have to solve:
The second line contains an integer T, denoting the number of test cases in the file.
Each of the following T lines will contain a test case:
For each test print the answer on a separate line.
If P = 1 and there is no solution, print the text “impossible” (quotes for clarity).
If P = 1 and there is a solution, print a possible coloring. The i-th character on the line should denote the color of the i-th character in S, encoded with ‘R’ for red, ‘B’ for blue and ‘G’ for green.
If P = 2, print the answer modulo 1,000,000,007.
For P = 1:
For P = 2:
1 3 ())(() ()(() ()))
GRBRBG BBRBG impossible
In the first case, both Theo and Radu will see the string “()()”.
In the second case, Theo will see the string “()” and Radu will see the string “()()”.
In the third case, there is no valid coloring.
2 2 6 100