No.2143 Only One Bracket
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 120
作問者 :
milkcoffee
/ テスター :
nok0
cpbm_p
タグ : / 解いたユーザー数 120
作問者 :
milkcoffee
/ テスター :
nok0
cpbm_p
問題文最終更新日: 2022-11-25 22:34:51
問題文
以下の条件を全て満たす $N$ 個の文字列の組 $(S_1, S_2 , \dots , S_N)$ を一つ求めてください。
- $S_i$ は
(,)からなる。 - $|S_i| \geq 1$
- $|S_1|+|S_2|+\dots + |S_N| \leq N^2$
- 以下を満たす $(1,2, \dots, N)$ の順列 $P=(P_1, P_2, \dots, P_N)$ がちょうど $1$ つ存在する。
- $S_{P_1} + S_{P_2} + \dots + S_{P_N}$ が括弧の対応が取れている文字列である。
ただし、文字列における「$+$」は単に文字列の結合を意味します。
また、括弧の対応が取れている文字列を、次のうちいずれかの条件を満たす文字列と定義します。
- 空文字列
- ある括弧の対応が取れている空でない文字列 $s,t$ が存在し、$s,t$ をこの順に連結した文字列
- ある括弧の対応が取れている文字列 $s$ が存在し、
(, $s$,)をこの順に連結した文字列
入力
$N$
- $2 \leq N \leq 8$
- $N$ は整数である
出力
$i$ 行目に $S_i$ を出力してください。
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされます。
サンプル
サンプル1
入力
2
出力
) (()
$P=(2,1)$ のとき、 $S_{P_1}+S_{P_2}=$ (()) であり、括弧の対応が取れている文字列になっています。
$S_{P_1}+S_{P_2}$ が括弧の対応が取れている文字列になるような順列 $P$ はこの $1$ つだけであるため、最後の条件を満たします。
他の条件も満たしているため、この出力は正解となります。
例えば、$S_1=$(), $S_2=$() としてしまうと、$S_1+S_2$, $S_2+S_1$ の $2$ 通りの場合で括弧の対応が取れている文字列になってしまうため不正解となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。