Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Communication

# 21603. 【PTR #1】双射

统计

这是一道通信题。

考虑在平面上从原点 $(0, 0)$ 走到 $(n, n)$,且每一步只能向右 $(\mathbf R)$ 与向上 $(\mathbf U)$ 的路径,容易发现每条路径的长度均为 $2n$,且其中恰好包含 $n$ 步向右, $n$ 步向上。众所周知,这样的路径总数共有 $\binom{2n}{n} = \frac{(2n)!}{n! \cdot n!}$ 种。

例如,$n = 2$ 时,共有以下 $6$ 种不同的路径:$\{ \mathbf{RRUU}, \mathbf{RURU}, \mathbf{RUUR}, \mathbf{URRU}, \mathbf{URUR}, \mathbf{UURR} \}$。

一个仅包含 () 的字符串 $U$ 被称为一个合法括号序列,当且仅当它可被通过如下方式递归定义:

  • 空串是合法括号序列
  • 如果 $S$ 是合法括号序列,则 $(S)$ 是合法括号序列。
  • 如果 $S$ 与 $T$ 均是合法括号序列,则 $ST$ 是合法括号序列。

考虑由恰好包含 $n$ 个左括号 ( 与 $n$ 个右括号 ) 的合法括号序列,众所周知,这样的括号序列共有 $C_n = \frac{1}{n+1} \binom{2n}{n}$ 种,其中 $C_n$ 为大家最喜欢的卡特兰数。

现在你希望构造任意一个反映了这一事实的双射。具体地,给定一个长为 $2n$,且包含恰好 $n$ 个 R 与 $n$ 个 U 的字符串 $S$,你需要构造一个包含 $n$ 对括号的合法括号序列 $U$ 与一个在 $[0, n]$ 中的整数 $k$。随后,给定你所构造的合法括号序列与整数 $k$,你需要复原最初的路径。

实现细节

这是一道 ejudge 风格的通信题。在这道题中,你的程序将在每个测试点被运行两次。在第一次运行中,你需要将描述路径的字符串编码为括号序列与整数 $k$;在第二次运行中,你需要将你编码的括号序列与整数 $k$ 复原为对应的路径。

第一次运行

在第一次运行中,输入的第一行包含一个字符串 path,表示这是对你的程序的第一次运行。

接下来一行,包含一个整数 $n$,表示路径长度的一半。

接下来一行,包含一个长度为 $2n$,且只包含字符 R 与字符 U 的字符串 $S$,表示你需要编码的路径。

在第一次运行中,你需要输出恰好两行。

输出的第一行包含一个长为 $2n$ 的合法括号序列 $U$。

接下来一行,包含一个在 $[0, n]$ 中的整数 $k$。

第二次运行

在第二次运行中,输入的第一行包含一个字符串 brackets,表示这是对你的程序的第二次运行。

接下来一行,包含一个整数 $n$,表示括号序列长度的一半。

接下来一行,包含一个长度为 $2n$,且只包含字符 ( 与字符 ) 的字符串 $S$,表示你所编码的合法括号序列。

接下来一行,包含一个整数 $k$,表示你所编码的整数 $k$。

在第二次运行中,你需要输出恰好一行。

输出一行一个长度为 $2n$ 的字符串,表示你所复原的原始路径。

样例一

First Input

path
2
RRUU

First Output

(())
0

Second Input

brackets
2
(())
0

Second Output

RRUU

样例二

First Input

path
3
RUURRU

First Output

(())()
3

Second Input

brackets
3
(())()
3

Second Output

RUURRU

子任务

  • Subtask 1 (10 points): $n \leq 3$
  • Subtask 2 (20 points): $n \leq 6$
  • Subtask 3 (70 points): 没有额外的限制

对于所有数据,保证 $1 \leq n \leq 300$。

qweq