Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | match.in, match.out | Sursă | CEOI 2016, Ziua 2 |
| Autor | Adrian Budau | Adăugată de |  Vlad Dumitru-Popescu •depevlad |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Match
Vom defini o secvenţă validă de paranteze ca pe un şir de caractere care poate fi:
- 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.
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ă:
- 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.
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ă:
- 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ă.
Intrare
Fişierul de intrare match.in conţine un şir S din N litere mici în prima linie.
Iesire
Î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ă.
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 ')'.
Exemplu
| 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. |
