O parantezare corectă se obţine aplicând una dintre următoarele reguli:
• şirul vid este o parantezare corectă;
• dacă S este o parantezare corectă, atunci (S) este o parantezare corectă, iar cele două paranteze ( şi ) care încadrează şirul S sunt denumite paranteze pereche;
• dacă S1, S2, … , Sk sunt parantezări corecte atunci şirul S1S2...Sk obţinut prin concatenarea acestora este o parantezare corectă.
De exemplu şirurile (), ()(), (()) şi (()())() reprezintă parantezări corecte, în timp ce )(, ()()( şi (()()))) nu sunt parantezări corecte.
Fie S un şir care reprezintă o parantezare corectă. Pentru fiecare dintre parantezele pereche din şirul S asociem un cost egal cu diferenţa dintre poziţia pe care se află în S paranteza închisă şi poziţia parantezei deschise pereche. Poziţiile în şir le considerăm numerotate începând cu 1. Costul total al unei parantezări corecte îl reprezintă suma costurilor tuturor parantezelor pereche din aceasta.
De exemplu, şirul (()()) este format din trei paranteze pereche, situate pe poziţiile 2 şi 3, apoi 4 şi 5, respectiv 1 şi 6. Costul total al parantezării este 3-2 + 5-4 + 6-1 = 7.
Numim operaţie swap interschimbarea a două paranteze situate în şir pe poziţii alăturate. Această operaţie este validă doar dacă şirul nou obţinut este la rândul său o parantezare corectă şi dacă noua parantezare are costul total strict mai mic decât cea iniţială.
Cerinţă
Scrieţi un program care citeşte o succesiune de N caractere reprezentând o parantezare corectă şi determină:
a) Costul total asociat parantezării citite
b) Costul minim al unei parantezări obţinute prin efectuarea unei singure operaţii swap valide asupra parantezării citite.
c) Numărul de posibilităţi de a efectua o singură operaţie swap validă asupra parantezării iniţiale pentru a obţine costul determinat conform cerinţei b).
Date de intrare
Fişierul de intrare swap.in conţine pe prima linie numărul natural N şi pe a doua linie o succesiune de N caractere reprezentând o parantezare corectă.
Date de ieşire
Fişierul de ieşire swap.out va conţine pe prima linie un număr natural reprezentând costul parantezării citite. A doua linie va conţine un număr natural reprezentând costul minim determinat conform cerinţei b) sau valoarea -1 când nu se poate efectua nici o operaţie swap validă asupra parantezării citite. A treia linie a fişierului va conţine un număr natural reprezentând răspunsul la cerinţa c) sau 0 dacă numărul afişat conform cerinţei b) a fost -1.
Restricţii
• 2 ≤ N ≤ 90000
• Pe fiecare dintre cele 3 linii ale fişierului de ieşire trebuie să se afle un singur număr întreg. Dacă numărul de pe prima linie este corect, se acordă 20% din punctajul testului. Dacă numărul de pe a doua linie este corect, se acordă 20% din punctaj. Dacă numărul de pe a treia linie este corect, se acordă 60% din punctaj.
Exemple
swap.in
swap.out
Explicaţii
8
()(())()
6
4
1
Pentru cerința a) costul parantezării este 2-1+6-3+5-4+8-7=6. Executând o operaţie swap între parantezele de pe poziţiile 4 și 5 se obține șirul ()()()() care are costul 4, aceasta fiind singura posibilitate de a obține acest cost.