A16643 · Bracket Groups

题目描述

一个“正规括号序列”是指可以转换为正确的算术表达式的括号序列。例如： - 括号序列 "()()" 和 "(())" 是正规的（转换后表达式分别为 "(1)+(1)" 和 "((1+1)+1)"）； - 括号序列 ")(", "(" 和 ")" 不是正规的。 现在给定 $n$ 个括号序列 $s_1, s_2, \dots, s_n$（不一定是正规括号序列），以及一个偶数 $k$。你的任务是将它们划分到若干组中，满足： - 每个括号序列恰好属于一个组； - 对于每一组，存在一个长度恰好为 $k$ 的正规括号序列，使得该组内的任意一个括号序列都不是这个正规括号序列的子串。 请问，最少需要多少组才能满足上述要求？如果无法实现，则输出 $-1$。否则，输出分组方案和每组对应的任意一个长度为 $k$ 的正规括号序列。如果存在多个最优方案，任意输出一个即可。

第一行包含两个整数 $n$ 和 $k$，$1 \le n \le 50$，$2 \le k \le 50$，$k$ 是偶数。 接下来的 $n$ 行中，第 $i$ 行包含一个括号序列 $s_i$（$2 \le |s_i| \le k$)，仅包含字符 '(' 和 ')'。

如果无法按照要求分组，输出 $-1$。 否则，第一行输出最小分组数 $m$。接下来 $m$ 组，每组包含三行： - 第一行包含一个长度为 $k$ 的正规括号序列； - 第二行包含一个整数 $g$，表示本组中括号序列的数量； - 第三行包含 $g$ 个整数，表示本组包含的括号序列在输入中的编号。 要求本组中任意一个括号序列都不是该正规括号序列的子串。每个编号 $1 \sim n$ 只出现一次。 若存在多个最优解，输出任意一个。

输入 #1

3 6
)))
(((
(())

输出 #1

1
(()())
3
1 2 3