O aplicaţie ce trebuie executată pe un calculator multi-procesor constă din N fragmente de cod independente, ce pot fi rulate în paralel. Fiecare fragment trebuie executat în totalitate pe un singur procesor. Din dorinţa de a paraleliza cât mai mult aplicaţia, fragmentele de cod au dimensiuni mici şi, în consecinţă, timpi de execuţie mici. Mai precis, execuţia fiecărui fragment durează UNUL sau DOUĂ cicluri de ceas pe un procesor de tipul Pentium IV.
Sistemul pe care urmează să fie executată aplicaţia constă din P procesoare. Spre deosebire de majoritatea sistemelor de acest fel, însă, cele P procesoare au viteze de execuţie diferite. Primul procesor este un Pentium IV şi este cel mai rapid. Al doilea procesor este de două ori mai lent decât primul, al treilea de trei ori mai lent … al i-lea procesor este de i ori mai încet decât primul. În aceste condiţii, timpul de execuţie al fiecărui fragment de cod diferă, în funcţie de procesorul pe care va fi executat. Să prespunem că un segment de cod are timpul de execuţie T (unde T este 1 sau 2) pe primul procesor. Atunci pe un procesor i, timpul său de execuţie va fi i*T.
Cerinţă
Ştiind că fragmentele de cod pot fi executate în orice ordine şi pe orice procesor şi că orice procesor poate executa, la un moment dat, un singur fragment de cod, determinaţi timpul minim după care se va termina execuţia aplicaţiei (adică a tuturor fragmentelor de cod). Timpul după care se termină aplicaţia este egal cu maximul dintre timpii după care fiecare procesor redevine disponibil. Timpul după care un procesor redevine disponibil este egal cu suma timpilor de execuţie a fragmentelor de cod rulate pe procesorul respectiv.
Date de intrare
Prima (şi singura) linie a fişierului de intrare proc.in conţine trei numere întregi, separate prin spaţii: N – numărul de fragmente de cod, K – numărul de fragmente de cod care au timpul de execuţie pe un Pentium IV egal cu 1 (implicit, N-K au timpul de execuţie egal cu 2) şi P – numărul de procesoare ale sistemului.
Date de ieşire
Fişierul proc.out va conţine o singură linie pe care se află timpul minim după care se termină de executat aplicaţia.
Restricţii şi precizări
0 ≤ K ≤ N ≤ 1 000 000 0001 ≤ P ≤ 65 535- Cel puţin
40%din teste vor aveaN ≤ 2 000şiP ≤ 2 000. - Cel puţin
70%din teste vor aveaN ≤ 65 535şiP ≤ 16 383.
Exemplu
proc.in
4 3 2
proc.out
4
Explicaţie
Pe primul procesor se execută un fragment de cod cu timpul de execuţie (calculat pe un Pentium IV) egal cu 1 şi un fragment de cod cu timpul de execuţie egal cu 2 => timpul după care acest procesor devine disponibil este 1*1 + 1*2 = 3. Pe al doilea procesor se execută două fragmente de cod cu timpul de execuţie (calculat pe un Pentium IV) egal cu 1 => timpul după care acest procesor devine disponibil este 2 [numărul de fragmente] * (2*1) [timpul de execuţie al fiecărui fragment pe procesorul 2] = 4.