Fişierul intrare/ieşire:rsp.in, rsp.outSursălot 2006
AutorMugurel Ionut AndreicaAdăugată deazotlichidAdrian Vladu azotlichid
Timp execuţie pe test0.125 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Rsp

Primaria orasului ioliPest este alimentata cu electricitate prin intermediul unei retele vechi de cateva zeci de ani, care are mari pierderi de putere pe linii. Reteaua este alcatuita din noduri si conexiuni intre unele perechi de noduri. Structura retelei este, insa, una speciala, asemanatoare retelelor de rezistente serie-paralel si contine doua noduri speciale, numite nodul stanga si nodul dreapta. Astfel, reteaua are o structura ce corespunde unuia dintre urmatoarele 3 cazuri:

  • 2 noduri unite printr-o conexiune (vom numi aceasta structura "retea de baza"); in figura, nodul stanga al acestei retele este marcat cu T1, iar nodul dreapta cu T2;

  • conectarea in serie a doua retele; considerand doua retele R1 si R2, acestea se conecteaza in serie suprapunand nodul dreapta al lui R1 peste nodul stanga al lui R2; nodul stanga al retelei rezultate este nodul stanga al lui R1, iar nodul dreapta al retelei rezultate este nodul dreapta al lui R2;

  • conectarea in paralel a doua retele; considerand doua retele R1 si R2, acestea se conecteaza in paralel suprapunand nodul stanga al lui R1 peste nodul stanga al lui R2 si nodul dreapta al lui R1 peste nodul dreapta al lui R2; nodul stanga al retelei rezultate este dat de suprapunerea nodurilor stanga ale retelelor R1 si R2, iar nodul dreapta al retelei rezultate este dat de suprapunerea nodurilor dreapta ale retelelor R1 si R2; 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").

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:

Retea de baza=B
Retea=Retea de baza
sau
Retea S Retea
sau
Retea P Retea
sau
(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 doua retele descrise in figurile anterioare (in afara "retelei de baza") corespund urmatoarelor doua siruri: (BSBSB)P(BSB)S(BSB), respectiv (BSBSB)PB.

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.

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.

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.

Exemplu

rsp.inrsp.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content