* 2 noduri unite printr-o conexiune (vom numi aceasta structura "retea de baza"); in figura, nodul stanga al acestei retele este marcat cu $T{~1~}$, iar nodul dreapta cu $T{~2~}$;
!problema/rsp?1.bmp!
* conectarea in serie a doua retele; considerand doua retele $R{~1~}$ si $R{~2~}$, acestea se conecteaza in serie suprapunand nodul dreapta al lui $R{~1~}$ peste nodul stanga al lui $R{~2~}$; nodul stanga al retelei rezultate este nodul stanga al lui $R{~1~}$, iar nodul dreapta al retelei rezultate este nodul dreapta al lui $R{~2~}$;
!problema/rsp?2.bmp!
* conectarea in paralel a doua retele; considerand doua retele $R{~1~}$ si $R{~2~}$, acestea se conecteaza in paralel suprapunand nodul stanga al lui R{~1~} peste nodul stanga al lui $R{~2~}$ si nodul dreapta al lui $R{~1~}$ peste nodul dreapta al lui $R{~2~}$; nodul stanga al retelei rezultate este dat de suprapunerea nodurilor stanga ale retelelor $R{~1~}$ si $R{~2~}$, iar nodul dreapta al retelei rezultate este dat de suprapunerea nodurilor dreapta ale retelelor $R{~1~}$ si $R{~2~}$; in urma conectarii in paralel pot rezulta conexiuni multiple intre nodul stanga si nodul dreapta al retelei rezultate (de exemplu, in cazul conectarii in paralel a doua "retele de baza").
!problema/rsp?3.bmp!
In vederea pregatirii integrarii in Uniunea Europeana, s-au primit fonduri pentru schimbarea retelei. Operatia de schimbare a retelei presupune, in prima etapa, eliminarea tuturor conexiunilor dintre nodurile retelei (urmand ca, ulterior, aceste conexiuni sa fie inlocuite cu unele mai performante). In urma calculelor efectuate, s-a ajuns la concluzia ca cea mai eficienta metoda de eliminare a conexiunilor din cadrul retelei este de a elimina unele noduri ale retelei impreuna cu toate conexiunile adiacente acestor noduri. Asadar, trebuie eliminata o submultime de noduri astfel incat orice conexiune a retelei sa aiba cel putin unul dintre capete in aceasta submultime. Evident, se doreste sa se elimine un numar minim de noduri.
Dandu-se o retea a carei structura respecta regulile precizate mai sus, determinati numarul minim de noduri ce trebuie eliminate pentru ca, odata cu ele, sa fie eliminate toate conexiunile existente in retea.
Reteaua este descrisa sub forma unui sir de caractere ce respecta urmatoarele reguli gramaticale:
Reţea de baz� = B
Reţea = Reţea de baz�
| @Retea de baza@ | = | B |
| @Retea@ | = | @Retea de baza@
sau
Reţea S Reţea
@Retea@ S @Retea@
sau
Reţea P Reţea
@Retea@ P @Retea@
sau
( Reţea )
(@Retea@) |
Caracterul $S$ reprezinta operatia de conectare in serie a doua retele, iar caracterul $P$ reprezinta operatia de conectare in paralel a doua retele. Se observa ca gramatica descrisa anterior este similara unei gramatici a expresiilor aritmetice, in care $S$ si $P$ sunt operatori binari (se aplica asupra a doua retele). In urma acestei observatii si pentru a evita ambiguitatile ce ar putea fi produse de unele siruri, vom considera ca operatorul $P$ are o prioritate mai mare decat operatorul $S$. Astfel, sirul $BPBSB$ corespunde unei conectari in paralel a doua "retele de baza", reteaua rezultata fiind apoi conectata in serie cu o alta "retea de baza" (sirul este echivalent cu $(BPB)SB$, unde existenta parantezelor specifica clar ordinea de aplicare a operatorilor).
Cele dou� retele descrise in figurile anterioare (in afara "retelei de baza") corespund urmatoarelor doua siruri: $(BSBSB)P(BSB)S(BSB)$, respectiv $(BSBSB)PB$.
Caracterul $S$ reprezinta operatia de conectare in serie a doua retele, iar caracterul $P$ reprezinta operatia de conectare in paralel a doua retele. Se observa ca gramatica descrisa anterior este similara unei gramatici a expresiilor aritmetice, in care $S$ si $P$ sunt operatori binari (se aplica asupra a doua retele). In urma acestei observatii si pentru a evita ambiguitatile ce ar putea fi produse de unele siruri, vom considera ca operatorul $P$ are o prioritate mai mare decat operatorul $S$. Astfel, sirul $BPBSB$ corespunde unei conectari in paralel a doua "retele de baza", reteaua rezultata fiind apoi conectata in serie cu o alta "retea de baza" (sirul este echivalent cu @(BPB)SB@, unde existenta parantezelor specifica clar ordinea de aplicare a operatorilor).
Cele doua retele descrise in figurile anterioare (in afara "retelei de baza") corespund urmatoarelor doua siruri: @(BSBSB)P(BSB)S(BSB)@, respectiv @(BSBSB)PB@.
h2. Date de intrare
...
Pe prima linie a fisierului de intrare se afla numarul intreg $T$, reprezentand numarul de retele ce vor fi descrise in continuare. Urmatoarele $T$ linii contin cate un sir de caractere ce reprezinta descrierea corecta a cate unei retele.
h2. Date de iesire
...
In fisierul de iesire veti afisa $T$ linii, reprezentand numarul minim de noduri ce trebuie eliminate din fiecare retea descrisa in fisierul de intrare. Primul numar afisat corespunde primei retele descrise, al doilea numar celei de-a doua retele descrise s.a.m.d.
h2. Restrictii
h2. Restrictii si precizari
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* Orice sir din fisierul de intare va contine cel mult $100000$ de caractere.
* Nici un sir din fisierul de intrare nu va contine spatii; sirurile sunt formate numai din caracterele $B$, $S$, $P$, $($ si $)$.
* Orice linie din fisierul de intrare are la sfarsit caracterul "linie noua".
* $60%$ din fisierele de test vor contine numai siruri avand lungimi ≤ $5000$ de caractere.
h2. Exemplu
table(example). |_. rsp.in |_. rsp.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
| 7
B
(BSBSB)P(BSB)S(BSB)
(BSBSB)PB
BPBPBPBPBPBPBPBPBPB
(BSB)P(BSB)P(BSB)P(BSB)P(BSB)
(BSBSB)P(BSBSB)P(BSBSB)P(BSBSB)P(BSBSB)
@BPBSBPBP(BSB)S(BSBSB)P(BSBPB)@
| 1
4
2
1
2
6
4 |
...
== include(page="template/taskfooter" task_id="rsp") ==
