Fişierul intrare/ieşire:swap.in, swap.outSursăONI 2013 baraj gimnaziu
AutorDana LicaAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Swap (baraj gimnaziu)

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

Î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.

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.

Exemplu

swap.inswap.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici