== include(page="template/taskheader" task_id="swap") ==
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ă S[~1~], S[~2~], … , S[~k~] sunt parantezări corecte atunci șirul S[~1~]S[~2~]...S[~k~] obținut prin concatenarea acestora este o parantezare corectă.
De exemplu șirurile $()$, $()()$, $<notextile>(())</notextile>$ și $<notextile>(()())()</notextile>$ reprezintă parantezări corecte, în timp ce $)($, $()()($ și $<notextile>(()())))</notextile>$ 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ă.
h2. 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).
Poveste și cerință...
h2. 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ă.
Fișierul de intrare $swap.in$ ...
h2. Date de ieșire
În 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.
În fișierul de ieșire $swap.out$ ...
h2. 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.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. 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.
|
table(example).
|_. swap.in |_. swap.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="swap") ==
