| Fişierul intrare/ieşire: | optic.in, optic.out | Sursă | Happy Coding 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | optic.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 |
