== include(page="template/taskheader" task_id="jobs") ==
Poveste si cerinta...
Intr-o fabrica exista $2$ activitati ce trebuie executate. Prima activitate consta din $S{~1~}$ pasi consecutivi identici, iar a doua activitate din $S{~2~}$ 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 $T{~1,K~}$, respectiv $T{~2,K~}$, 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 $TA{~1~}$ cand se termina executia ultimului pas al primei activitati si momentul $TA{~2~}$ cand se termina executia ultimului pas al celei de-a doua activitati. Directorul fabricii doreste sa minimizeze suma $TA{~1~} + TA{~2~}$.
Scrieti un program care determina valoarea minima pentru suma $TA{~1~} + TA{~2~}$.
h2. 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$ $S{~1~}$ $S{~2~}$, 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: $T{~1,K~}$ si $T{~2,K~}$ cu semnificatia din enunt. Va exista o linie goala inaintea fiecarui set de date de test din fisier.
h2. 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 $TA{~1~} + TA{~2~}$ pentru cel de-al $i$-lea set de date de test.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 100$
* $1 ≤ S{~1~}, S{~2~} ≤ 7$
* $1 ≤ T{~1,K~}, T{~2,K~} ≤ 1.000.000$
h2. Exemplu
table(example). |_. jobs.in |_. jobs.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicatie
...
In primul set de date, primul (si singurul) muncitor executa primii $2$ pasi ai primei activitati si termina la momentul $20$ {$(TA{~1~} = 20)$}. Apoi, incepand de la momentul $20$, el executa cei $3$ pasi ai celei de-a doua activitati si termina la momentul $80$ {$(TA{~2~} = 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$ {$(TA{~2~} = 18)$}. Incepand de la momentul $0$, muncitorul $#3$ executa primii $3$ pasi ai primei activitati, terminand la momentul $18$ (ce coincidenta :) ). Apoi, al $4$-lea pas al primei activitati este executat de muncitorul $#2$, de la momentul $18$ pana la momentul $23$ {$(TA{~1~} = 23)$}. Astfel, raspunsul este $18 + 23 = 41$.
== include(page="template/taskfooter" task_id="jobs") ==
