Avem un calculator cu N
procesoare. La un moment dat unul dintre procesoare are o informatie ce trebuie
sa ajunga la toate celalalte procesoare.
Procesoarele comunica doar doua cate doua, insa pot fi mai multe perechi de
procesoare care comunica simultan. De asemenea pentru comunicarea unui mesaj
intre doua procesoare se stie ca este nevoie de M
microsecunde pentru trimiterea sau primirea unui mesaj, L
microsecunde pentru ca mesajul sa ajunga de la un procesor la altul (dupa ce
a fost trimis si inainte ca celalalt procesor sa-l primeasca). De asemenea intre
doua mesaje consecutiv trimise trebuie sa treaca cel putin G
microsecunde.
Se considera momentul de timp 0, in care unul din procesoare are informatia si vrea sa o transmita. De asemenea toate procesoarele vor fi ocupate doar cu transmisia sau receptia de mesaje (nu se executa alte programe pe ele).
Cerinta
Scrieti un program care afla timpul minim necesar (in microsecunde) comunicarii informatiei la toate procesoarele.
Date de intrare
Pe prima linie a fisierului de intrare logn.in
sunt scrise numerele L, M, G si N separate
printr-un spatiu (numere intregi nenegative).
Date de iesire
Prima linie a fisierului logn.out va contine timpul minim (in microsecunde, intreg nenegativ) comunicarii informatiei la toate procesoarele.
Restrictii
1 <= N <= 30000
1 <= L, M, G <= 10000
Exemplu
logn.in
logn.out
Comentarii
6 2 4 8
24
Procesorul 1 (care presupunem ca are informatia initiala) formateaza mesajul, iar in momentul 2 il trimite spre procesorul 2. Procesorul 2 primeste in mesajul in momentul 8 (2+6) si il are disponibil in momentul 10 (8+2). De asemenea procesorul 1 mai trimite mesajul spre procesoarele 3,4 si 5, in momentele 4, 8, 12. Ele vor avea mesajul disponibil in momentele 14, 18 si respectiv 22. Procesorul 2 trimite mesajul la procesoarele 6 si 7 (la momentul 10, adica cand il are disponibil si 14), care il vor avea disponibil in momentele 20 si respectiv 24. Procesorul 3 trimite mesajul spre procesorul 8 care il va avea in momentul 24.