Fişierul intrare/ieşire:jobs.in, jobs.outSursă.campion 2005
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Jobs

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 T1,K, respectiv T2,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 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.

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: T1,K si T2,K 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

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 100
  • 1 ≤ S1, S2 ≤ 7
  • 1 ≤ T1,K, T2,K ≤ 1.000.000

Exemplu

jobs.injobs.out
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

Explicatie

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 :) ). 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content