Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rsp.in, rsp.out | Sursă | lot 2006 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Adrian Vladu •azotlichid |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
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:
Reţea de baz� = B
Reţea = Reţea de baz�
sau
Reţea S Reţea
sau
Reţea P Reţea
sau
( Reţea )
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 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: P(BSB)S(BSB), respectiv PB.
Date de intrare
...
Date de iesire
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| rsp.in | rsp.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
