Bracket-and-bar Sequences

시간 제한2초메모리 제한1024 MB

요약

연결과 (A|B) 감싸기 규칙으로 만든 괄호와 막대 문자열을 길이별로 나열하고, 문자열과 정수를 서로 대응시킨다.

난이도: 보통10점 중 6점
유형: 구현, 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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:

$\varepsilon \in R$ (empty string)
$A, B \in R \Rightarrow AB \in R$ (concatenation)
$A, B \in R \Rightarrow$ ( $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.

예제2

예제 1

입력

encode
3
1
(|)
4
((((|)|)|)|)
5
(|(|))((|(|))|)

예상 출력

123
111123232323
121233112123323

예제 2

입력

decode
3
1
123
4
111123232323
5
121233112123323

예상 출력

(|)
((((|)|)|)|)
(|(|))((|(|))|)