| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 10 | 5 | 3 | 75.000% |
Let us define the set of regular bracket-and-bar sequences $R$ recursively. It is the set of strings that can be obtained following only the rules below:
($A$|$B$)$ \in R$For example, the sequences containing two triples "(|)" look as folows: "((|)|)", "(|(|))", "(|)(|)".
Establish a correspondence between regular bracket-and-bar sequences of certain length and integers, and implement that correspondence.
In this problem, your solution will be run twice on each test. Each line of input is terminated by an end-of-line character.
During the first run, the solution encodes bracket-and-bar sequences as integers. The first line contains the word "encode". The second line contains an integer $t$: the number of test cases (1ドル \le t \le 1000$). Each test case is given on two lines: the first line contains an integer $n$ which is the number of "(|)" triples in the sequence (1ドル \le n \le 25$), and the second line contains 3ドル n$ characters without spaces, constituting a reqular bracket-and-bar sequence with $n$ triples.
Print $t$ lines, one for each test case. On the $i$-th line, print an integer $x_i$ which you chose to encode the $i$-th sequence from the input (0ドル \le x_i \le 2 \cdot 10^{18}$).
During the second run, the solution decodes bracket-and-bar sequences from integers. The first line contains the word "decode". The second line contains an integer $t$: the number of test cases (1ドル \le t \le 1000$). Each test case is given on two lines: the first line contains an integer $n$ which is the number of "(|)" triples in the sequence (1ドル \le n \le 25$), and the second line contains the integer printed by your solution for this test case during the first run.
Print $t$ lines, one for each test case. On the $i$-th line, print the bracket-and-bar sequence from the $i$-th test case.
For each test, the input during the second run depends on the solution's output during the first run.
Below we show two runs of a certain solution on the first test. It can be seen that this solution encodes the characters by digits 1ドル,ドル 2ドル,ドル and 3ドル,ドル and just prints the resulting string of digits as the encoding integer. Unfortunately, for large $n,ドル the strings will become too long.
encode 3 1 (|) 4 ((((|)|)|)|) 5 (|(|))((|(|))|)
123 111123232323 121233112123323
decode 3 1 123 4 111123232323 5 121233112123323
(|) ((((|)|)|)|) (|(|))((|(|))|)