Numim
SCP (secventã corect parantezatã) o secventã formatã
din paranteze rotunde deschise si închise care poate fi formatã
aplicând urmãtoarele reguli:
1. Sirul vid este SCP
2. Dacã S este
SCP atunci (S) este de
asemenea SCP
3. Dacã A si B
sunt SCP, atunci AB este
SCP.
Sã considerãm un sir constituit din paranteze rotunde
si pãtrate (deschise si închise). Asupra acestui sir putem
aplica urmãtoarele operatii:
1. orice parantezã pãtratã deschisã poate
fi înlocuitã cu 0,
1, 2
sau mai multe paranteze rotunde deschise.
2. orice parantezã pãtratã închisã
poate fi înlocuitã cu 0,
1, 2
sau mai multe paranteze rotunde închise.
Observati cã este permisã înlocuirea unei paranteze
pãtrate cu 0 paranteze
rotunde (adicã este permisã stergerea ei).
Cerinţă
Dat fiind
un sir format din paranteze pãtrate si rotunde, scrieti un program
care sã determine o secventã corect parantezatã de
lungime minimã ce se poate obtine din sirul dat aplicând
operatiile descrise în enunt.
Date de intrare
Fisierul de intrare
scp.in contine pe prima
linie un sir format din paranteze rotunde si pãtrate.
Date de ieşire
Fisierul de
iesire scp.out va contine
o singura linie pe care va fi scrisã o secventã corect parantezatã
de lungime minimã ce se poate obtine din sirul dat aplicând
operatiile descrise în enunt. Dacã problema nu are solutie,
veti afisa pe prima linie cuvântul IMPOSIBIL.
Restricţii
0<Lungimea
sirului dat<=2000
Dacã
existã mai multe solutii de lungime minimã, afisati
pe oricare dintre acestea.
Exemple
scp.in
scp.out
Explicaţii
[)())(]()]
(()())()()
Prima
parantezã pãtratã deschisã este înlocuitã
de douã paranteze rotunde deschise.
Prima parantezã pãtratã închisã
este înlocuitã de o parantezã rotundã
deschisã.
A doua parantezã pãtratã închisã
este înlocuitã de 0 paranteze rotunde deschise (adicã
este stearsã).