Fișierul intrare/ieșire swap.in, swap.out Sursă ONI 2013 baraj gimnaziu
Autor Dana Lica Adăugată de avatar Marcela Marcela Marcela
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii