Diferențe pentru problema/swap între reviziile #24 si #14

Swap (baraj gimnaziu)

swap

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

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.

h2. Exemplu

table(example).

table(example).

|_. swap.in |_. swap.out |_. Explicații |
| 8
()(())()