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
1
<= T <= 20
1
<= N <= 100
1
<= S1 <= 7
1
<= S2 <= 7
1
<= T1K <= 1 000 000
1
<= T2K <= 1 000 000
Exemplu
jobs.in
jobs.out
Explicatie
4
1 2 3 10 20
3
5 7 10 20 15 16 17 18
4
3 6 10 12 8 9 16 11 13 20
4
4 6 7 12 5 3 6 5 1000000 1000000
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.