Intr-o fabrica
exista 2 activitati ce trebuie executate. Prima activitate consta din S1
pasi consecutivi identici, iar a doua activitate din S2
pasi consecutivi identici. In fabrica lucreaza N
persoane. Fiecare persoana poate executa orice pas al oricareia dintre cele
2 activitati. Pentru fiecare persoana K
se cunosc timpii T1K,
respectiv T2K, ce
reprezinta durata de timp necesara pentru ca acea persoana sa execute un pas
din prima, respectiv un pas din a doua activitate. Fiecare pas al oricareia
dintre cele 2 activitati trebuie executat de exact o persoana. O persoana poate
executa mai multi pasi din ambele activitati, insa numai un pas la un moment
dat.
Executia celor 2 activitati se considera ca incepe dimineata devreme, dupa ce
toti cei N muncitori au sosit
la fabrica (la momentul de timp 0).
O data ce un muncitor a inceput executia unuia dintre pasi, el nu mai poate
fi intrerupt pana cand nu termina de executat pasul respectiv. Pauze (timpi
de asteptare) pot exista numai inaintea inceputului executiei fiecarui pas al
oricareia dintre cele 2 activitati.
Sa consideram momentul TA1
cand se termina executia ultimului pas al primei activitati si momentul TA2
cand se termina executia ultimului pas al celei de-a doua activitati. Directorul
fabricii doreste sa minimizeze suma TA1
+ TA2.
Cerinta
Scrieti un program care determina valoarea minima pentru suma TA1 + TA2.
Date de intrare
Prima linie a fisierului de intrare jobs.in contine numarul de seturi de date de test T aflate in fisier. Urmatoarele linii descriu cele T seturi de date de test. Prima linie a fiecarui set de date de test contine 3 numere naturale separate prin cate un spatiu N S1 S2, care reprezinta numarul de persoane ce lucreaza la fabrica, numarul de pasi ai primei activitati si respectiv numarul de pasi ai celei de-a doua activitati. Urmatoarele N linii ale setului de date de test contin fiecare cate 2 numere intregi separate prin spatiu: T1K si T2K cu semnificatia din enunt. Va exista o linie goala inaintea fiecarui set de date de test din fisier.
Date de iesire
Fisierul de iesire jobs.out va contine T linii, cate una pentru fiecare set de date de test din fisierul de intrare. Pe linia i va fi afisata valoarea minima posibila pentru suma TA1 + TA2 pentru cel de-al i-lea set de date de test.
Restrictii si precizari
jobs.in | jobs.out | Explicatie |
4
1 2 3 3 5 7 4 3 6 4 4 6 |
100 162 84 41 |
In primul set de date, primul (si singurul) muncitor executa primii 2 pasi ai primei activitati si termina la momentul 20 (TA1 = 20). Apoi, incepand de la momentul 20, el executa cei 3 pasi ai celei de-a doua activitati si termina la momentul 80 (TA2 = 80). Raspunsul este 20 + 80 = 100. In al doilea set de date, muncitorul #1 executa toti cei 5 pasi ai primei activitati, terminand la momentul 50, iar muncitorul #2 executa toti cei 7 pasi ai celei de-a doua activitati, terminand la momentul 112. Raspunsul este 50 + 112 = 162. In al treilea set de date, muncitorul #1 executa toti cei 3 pasi ai primei activitati, terminand la momentul 30, iar muncitorul #2 executa toti cei 6 pasi ai celei de-a doua activitati, terminand la momentul 54. Astfel, raspunsul este 30 + 54 = 84. In al patrulea set
de date, muncitorul #2 executa toti cei 6 pasi ai celei de-a doua activitati,
terminand la momentul 18 (TA2
= 18). Incepand de la momentul 0, muncitorul #3 executa primii 3 pasi
ai primei activitati, terminand la momentul 18 (ce coincidenta J).
Apoi, al 4-lea pas al primei activitati este executat de muncitorul #2,
de la momentul 18 pana la momentul 23 (TA1
= 23). Astfel, raspunsul este 18 + 23 = 41.
|
Timp maxim de executie/test: 0.1 secunde
Mugurel Ionut
Andreica
Universitatea Politehnica
Bucuresti
Contact:mugurel_ionut@yahoo.com