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

Swap (baraj gimnaziu)

swap

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

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ă.
h2. Cerință

h2. Exemplu

table(example).

table(example).

|_. swap.in |_. swap.out |_. Explicații |

| 8
()(())()
| 6
4
1

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

aceasta fiind singuraposibilitate de a obține acest cost.

|
== include(page="template/taskfooter" task_id="swap") ==