== include(page="template/taskheader" task_id="match") ==
Poveste şi cerinţă...
Vom defini o secvenţă validă de paranteze ca pe un şir de caractere care poate fi:
h2. Date de intrare
* Un şir vid;
* Un şir $(B)$, unde $B$ o secvenţă validă de paranteze.
* $LR$, concatenarea a două şiruri $L$ şi $R$ ambele fiind secvenţe valide de paranteze.
Fişierul de intrare $match.in$ ...
Fie $B$ be o secvenţă validă de paranteze de lungime $N$. Vom defini $B(i)$ ca a $i$-ulea caracter din secvenţa $B$. Pentru doi indici $i$ şi $j$, $1 ≤ i < j ≤ N$, spunem că $B(i)$ şi $B(j)$ formează o potrivire de paranteze dacă:
h2. Date de ieşire
* $B(i) = '('$ şi $B(j) = ')'$;
* $i = j-1$, sau subsecvenţa $C = B(i + 1)B(i + 2) … B(j - 1)$ este o secvenţă validă de paranteze.
În fişierul de ieşire $match.out$ ...
Fie $S$ un şir de litere mici din alfabetul englez. Vom defini $S(i)$ ca a $i$-ulea caracter din secvenţa $S$. Spunem că o secvenţă validă de paranteze $B$ se potriveşte cu $S$ dacă:
h2. Restricţii
* $B$ are aceeaşi lungime ca şi $S$;
* Pentru orice pereche de indici $i$ şi $j$, $i < j$, dacă parantezele $B(i)$ şi $B(j)$ formează o potrivire, atunci $S(i) = S(j)$.
* $... ≤ ... ≤ ...$
Pentru un şir $S$ format din $N$ litere mici, găseşte cea mai mică, în sens lexicografic, secvenţă validă de paranteze, care se potriveşte cu $S$, sau scrie $-1$ dacă o asemenea secvenţă nu există.
h2. Exemplu
h2. Intrare
Fişierul de intrare $match.in$ conţine un şir $S$ din $N$ litere mici în prima linie.
h2. Iesire
table(example). |_. match.in |_. match.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
În fişierul de ieşire $match.out$ vei scrie un şir $B$ din $N$ caractere care reprezintă cea mai mica în sens lexicografic secvenţă validă de paranteze, care se potriveşte cu şirul de intrare, sau $-1$ dacă o asemenea secvenţă nu există.
h3. Explicaţie
h2. Restrictii si Precizari:
* $2 ≤ N ≤ 100000$
* $Pentru testele în valoare de 10 puncte N ≤ 18.$
* $Pentru testele în valoare de 27 puncte N ≤ 2 000.$
* $Spunem că o secvenţă de paranteze A este mai mică în sens lexicografic decât secvenţa de paranteze B dacă există un indice i, 1 ≤ i ≤ N, astfel încât Aj = Bj pentru fiecare j < i, şi A(i) < B(i).$
* $Caracterul '(' se consideră lexicografic mai mic decât caracterul ')'.$
h2. Exemplu
...
table(example). |_. match.in |_. match.out |_. Explicatie |
| abbaaa
| (()())
| O altă secvenţă validă de paranteze este (())(), dar aceasta nu este cea mai mica în sens lexicografic. |
| abab
| -1
| Nu există nici o secvenţă validă de paranteze, care se potriveşte cu şirul dat.
|
== include(page="template/taskfooter" task_id="match") ==
