F - Bracket Sequencing
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
以下のいずれかの条件を満たす文字列を括弧列と定義します。
- 空文字列
- ある括弧列 A が存在して、
(
, A,)
をこの順に連結した文字列 - ある空でない括弧列 A, B が存在して、A, B をこの順に連結した文字列
N 個の文字列 S_i が与えられます。S_i 全てを好きな順序で連結するとき、括弧列を構成することはできますか。
制約
- 1 \leq N \leq 10^6
- S_i の文字列長の合計は 10^6 以下
- S_i は
(
,)
のみからなる空でない文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 : S_N
出力
S_i を任意の順序で連結するとき、括弧列を構成できるなら Yes
、できないなら No
を出力せよ。
入力例 1
2 ) (()
出力例 1
Yes
(()
, )
の順に連結すると括弧列になります。
入力例 2
2 )( ()
出力例 2
No
入力例 3
4 ((())) (((((( )))))) ()()()
出力例 3
Yes
入力例 4
3 ((( ) )
出力例 4
No
Score : 600 points
Problem Statement
A bracket sequence is a string that is one of the following:
- An empty string;
- The concatenation of
(
, A, and)
in this order, for some bracket sequence A ; - The concatenation of A and B in this order, for some non-empty bracket sequences A and B /
Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?
Constraints
- 1 \leq N \leq 10^6
- The total length of the strings S_i is at most 10^6.
- S_i is a non-empty string consisting of
(
and)
.
Input
Input is given from Standard Input in the following format:
N S_1 : S_N
Output
If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes
; otherwise, print No
.
Sample Input 1
2 ) (()
Sample Output 1
Yes
Concatenating (()
and )
in this order forms a bracket sequence.
Sample Input 2
2 )( ()
Sample Output 2
No
Sample Input 3
4 ((())) (((((( )))))) ()()()
Sample Output 3
Yes
Sample Input 4
3 ((( ) )
Sample Output 4
No