| Fişierul intrare/ieşire: | cast.in, cast.out | Sursă | Lot Suceava 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
Cerinta
Determinati durata de timp minima (corespunzatoare unei strategii inteligente de broadcast) dupa care informatiile ajung la toate calculatoarele.
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 intotdeauna egala cu 0.
Date de iesire
In fisierul cast.out veti afisa T linii, cate una pentru fiecare set de date de test. Pe linia i va fi scris un numar natural Tmin reprezentand durata minima dupa care informatiile pot ajunge la toate calculatoarele pentru al i-lea set de test din fisierul de intrare.
Restrictii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 12
- 0 ≤ Durata de transmitere a informatiilor intre oricare doua calculatoare ≤ 10000
Exemplu
| cast.in | cast.out |
|---|---|
| 2 4 0 4 2 1 4 0 16 13 7 8 0 9 10 11 3 0 2 0 0 10 0 | 5 0 |
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.
