Fişierul intrare/ieşire:optic.in, optic.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.3 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Optic

N switch-uri, numerotate de la 1 la N, sunt interconectate intr-o retea prin conexiuni din fibra optica. Reteaua are o structura arborescenta. Radacina arborelui este reprezentata de switch-ul numerotat cu 1, pe care il consideram situat pe nivelul cel mai de sus din arbore. O conexiune leaga 2 switch-uri si este unidirectionala (orientata de la switch-ul aflat pe un nivel superior catre cel aflat pe un nivel inferior). Switch-ul cu numarul 1 trebuie sa transmita niste informatii foarte importante referitoare la starea retelei tuturor celorlalte switch-uri. Pentru a realiza acest lucru, trebuie stabilita o strategie inteligenta de broadcast (transmisie catre toate switch-urile).

La orice moment de timp, un switch A care detine informatiile (initial, la momentul 0, doar switch-ul 1 detine informatiile) poate stabili o cale optica pana la un switch B aflat in subarborele switch-ului A. Calea optica consta din switch-urile A, B si toate celelalte switch-uri aflate pe drumul unic (si orientat) de la A la B. Stabilirea caii optice dureaza 1 unitate de timp, transmisia informatiilor realizandu-se apoi instantaneu. La finalul transmisiei pe calea optica stabilita, doar switch-ul B va primi informatiile, nu si celelalte switch-uri intermediare de pe drumul de la A la B. O restrictie suplimentara generata de modul de functionare al switch-urilor este ca, la orice moment de timp, orice switch poate face parte din cel mult o cale optica. Asadar, la fiecare moment de timp, caile optice stabilite pentru transmiterea informatiilor trebuie sa fie disjuncte din punct de vedere al switch-urilor ce fac parte din ele. Timpul de transmitere a informatiilor al unei strategii de broadcast este momentul de timp maxim la care unul din switch-uri a primit informatiile.

Determinati o strategie de broadcast cu timp minim de transmitere a informatiilor.

Date de intrare

Fisierul de intrare optic.in contine, pe prima linie, numarul natural N, reprezentand numarul de switch-uri din retea. Urmatoarele N-1 linii contin cate doua numere naturale distincte A si B avand semnificatia ca exista o conexiune directa orientata de la A la B.

Date de iesire

Fisierul de iesire optic.out va contine, pe prima linie, timpul minim T de transmitere a informatiilor. In continuare, pentru fiecare moment de timp M de la 0 la T-1 va fi afisat un numar natural C, reprezentand numarul de cai optice stabilite la momentul M, urmat de C linii continand 2 numere naturale separate printr-un spatiu, A si B, avand semnificatia ca s-a stabilit o cale optica de la switch-ul A la switch-ul B, la momentul M, in vederea transmiterii informatiilor.

Restrictii

  • 1 ≤ N ≤ 333

Exemplu

optic.inoptic.out
6
1 2
1 3
3 4
4 5
5 6
3
1
1 3
2
1 2
3 5
2
3 4
5 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content