Fişierul intrare/ieşire:cast.in, cast.outSursăLot Suceava 2007
AutorMugurel Ionut AndreicaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incast.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content