cast

Cast

== include(page="template/taskheader" task_id="cast") ==

$N$ calculatoare, numerotate de la 1 la N, sunt interconectate intr-o retea. Calculatorul $1$ detine niste informatii pe care doreste sa le transmita tuturor celorlalte calculatoare (acest tip de transmisie de informatii este cunoscut sub numele de _broadcast_). Pentru aceasta, programul care ruleaza pe calculatorul $1$ trebuie sa stabileasca o strategie inteligenta de transmitere a informatiilor, astfel incat acestea sa ajunga la toate celelalte calculatoare intr-un timp cat mai scurt. Oricare doua calculatoare pot comunica intre ele si se cunoaste durata de transmisie a informatiilor de la orice calculator $i$ la orice calculator $j$ (durata transmisiei de la $i$ la $j$ poate fi diferita de durata transmisiei de la $j$ la $i$). Din momentul in care un calculator $i$ a primit informatiile, acesta le poate transmite mai departe altor calculatoare. La orice moment de timp, un calculator poate transmite informatii numai unui singur alt calculator. Asadar, daca un calculator $i$ doreste sa transmita informatii calculatoarelor $j$ si $k$, el va trebui sa transmita intai informatiile calculatorului $j$, iar dupa ce acestea au fost receptionate (dupa o durata de timp egala cu durata transmisiei de la $i$ la $j$), ele pot fi transmise apoi calculatorului $k$. In mod evident, transmisiile intre doua perechi diferite de calculatoare se pot realiza in paralel. Durata de timp dupa care informatiile ajung la toate calculatoarele este cel mai mare moment de timp la care un calculator primeste informatiile (considerand ca procesul de transmitere a informatiilor incepe la momentul $0$).

$N$ calculatoare, numerotate de la $1$ la $N$, sunt interconectate intr-o retea. Calculatorul $1$ detine niste informatii pe care doreste sa le transmita tuturor celorlalte calculatoare (acest tip de transmisie de informatii este cunoscut sub numele de _broadcast_). Pentru aceasta, programul care ruleaza pe calculatorul $1$ trebuie sa stabileasca o strategie inteligenta de transmitere a informatiilor, astfel incat acestea sa ajunga la toate celelalte calculatoare intr-un timp cat mai scurt. Oricare doua calculatoare pot comunica intre ele si se cunoaste durata de transmisie a informatiilor de la orice calculator $i$ la orice calculator $j$ (durata transmisiei de la $i$ la $j$ poate fi diferita de durata transmisiei de la $j$ la $i$). Din momentul in care un calculator $i$ a primit informatiile, acesta le poate transmite mai departe altor calculatoare. La orice moment de timp, un calculator poate transmite informatii numai unui singur alt calculator. Asadar, daca un calculator $i$ doreste sa transmita informatii calculatoarelor $j$ si $k$, el va trebui sa transmita intai informatiile calculatorului $j$, iar dupa ce acestea au fost receptionate (dupa o durata de timp egala cu durata transmisiei de la $i$ la $j$), ele pot fi transmise apoi calculatorului $k$. In mod evident, transmisiile intre doua perechi diferite de calculatoare se pot realiza in paralel. Durata de timp dupa care informatiile ajung la toate calculatoarele este cel mai mare moment de timp la care un calculator primeste informatiile (considerand ca procesul de transmitere a informatiilor incepe la momentul $0$).

h2. Cerinta

h2. Date de intrare

Fisierul de intrare $cast.in$ contine pe prima linie numarul natural $T$, reprezentand numarul de seturi de date de test. In continuare, urmeaza descrierea celor $T$ seturi. Prima linie din cadrul fiecarui set de test contine numarul natural $N$, reprezentand numarul de calculatoare. Urmatoarele $N$ linii contin cate $N$ numere intregi, separate prin cate un spatiu. Al $j$-lea numar de pe a $i$-a dintre aceste linii contine durata de transmisie a informatiilor de la calculatorul $i$ la calculatorul $j$. Durata transmisiei de la un calculator la el insusi va fi întotdeauna egala cu 0.

Fisierul de intrare $cast.in$ contine pe prima linie numarul natural $T$, reprezentand numarul de seturi de date de test. In continuare, urmeaza descrierea celor $T$ seturi. Prima linie din cadrul fiecarui set de test contine numarul natural $N$, reprezentand numarul de calculatoare. Urmatoarele $N$ linii contin cate $N$ numere intregi, separate prin cate un spatiu. Al $j$-lea numar de pe a $i$-a dintre aceste linii contine durata de transmisie a informatiilor de la calculatorul $i$ la calculatorul $j$. Durata transmisiei de la un calculator la el insusi va fi intotdeauna egala cu 0.

h2. Date de iesire

h3. Explicatie

...

In cazul primului set de test, la momentul $0$, calculatorul $1$ incepe sa trimita informatiile calculatorului $4$ (transmisia dureaza pana la momentul $1$). La momentul $1$, calculatorul $1$ incepe sa transmita informatiile calculatorului $2$ (transmisia dureaza pana la momentul $5$), iar calculatorul $4$ incepe sa transmita informatiile calculatorului $3$ (transmisia dureaza pana la momentul $4$). Momentele de timp la care cele $4$ calculatoare afla informatiile sunt: $0$, $5$, $4$ si $1$.
 
In cazul celui de-al doilea set de test, la momentul $0$ calculatorul $1$ incepe sa transmita informatiile calculatorului $2$, iar transmisia se termina tot la momentul $0$.

== include(page="template/taskfooter" task_id="cast") ==

1894