.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » jobs

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
jobs


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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.

 

Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti
Contact:mugurel_ionut@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, scara1, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
surse trimise | ajutor