Fişierul intrare/ieşire:match.in, match.outSursăCEOI 2016, Ziua 2
AutorAdrian BudauAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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.inmatch.outExplicatie
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?