Fişierul intrare/ieşire:proc.in, proc.outSursăONI 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Proc

O aplicatie ce trebuie executata pe un calculator multi-procesor consta din N fragmente de cod independente, ce pot fi rulate in paralel. Fiecare fragment trebuie executat in totalitate pe un singur procesor. Din dorinta de a paraleliza cat mai mult aplicatia, fragmentele de cod au dimensiuni mici si, in consecinta, timpi de executie mici. Mai precis, executia fiecarui fragment dureaza UNUL sau DOUA cicluri de ceas pe un procesor de tipul Pentium IV.

Sistemul pe care urmeaza sa fie executata aplicatia consta din P procesoare. Spre deosebire de majoritatea sistemelor de acest fel, insa, cele P procesoare au viteze de executie diferite. Primul procesor este un Pentium IV si este cel mai rapid. Al doilea procesor este de doua ori mai lent decat primul, al treilea de trei ori mai lent ... al i-lea procesor este de i ori mai incet decat primul. In aceste conditii, timpul de executie al fiecarui fragment de cod difera, in functie de procesorul pe care va fi executat. Sa prespunem ca un segment de cod are timpul de executie T (unde T este 1 sau 2) pe primul procesor. Atunci pe un procesor i, timpul sau de executie va fi i*T.

Cerinta

Stiind ca fragmentele de cod pot fi executate in orice ordine si pe orice procesor si ca orice procesor poate executa, la un moment dat, un singur fragment de cod, determinati timpul minim dupa care se va termina executia aplicatiei (adica a tuturor fragmentelor de cod). Timpul dupa care se termina aplicatia este egal cu maximul dintre timpii dupa care fiecare procesor redevine disponibil. Timpul dupa care un procesor redevine disponibil este egal cu suma timpilor de executie a fragmentelor de cod rulate pe procesorul respectiv.

Date de intrare

Prima (si singura) linie a fisierului de intrare proc.in contine trei numere intregi, separate prin spatii: N - numarul de fragmente de cod, K - numarul de fragmente de cod care au timpul de executie pe un Pentium IV egal cu 1 (implicit, N-K au timpul de executie egal cu 2) si P - numarul de procesoare ale sistemului.

Date de iesire

Fisierul proc.out va contine o singura linie pe care se afla timpul minim dupa care se termina de executat aplicatia.

Restrictii si precizari

  • 0 ≤ K ≤ N ≤ 1.000.000.000
  • 1 ≤ P ≤ 65.535

Exemplu

proc.inproc.out
4 3 24

Explicatie

Pe primul procesor se executa un fragment de cod cu timpul de executie (calculat pe un Pentium IV) egal cu 1 si un fragment de cod cu timpul de executie egal cu 2 => timpul dupa care acest procesor devine disponibil este 1*1 + 1*2 = 3. Pe al doilea procesor se executa doua fragmente de cod cu timpul de executie (calculat pe un Pentium IV) egal cu 1 => timpul dupa care acest procesor devine disponibil este 2 [numarul de fragmente] * (2*1) [timpul de executie al fiecarui fragment pe procesorul 2] = 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content