Fişierul intrare/ieşire:tproc.in, tproc.outSursăStelele Informaticii 2007-2008, Clasele 11-12
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tproc

Un sistem multiprocesor este alcatuit din K procesoare. Pe acest sistem trebuie executata o aplicatie ce consta din N procese independente, numerotate de la 1 la N. Fiecare proces trebuie executat in totalitate pe unul din cele K procesoare. Deoarece unele procese folosesc date din locatii de memorie total diferite, daca anumite perechi de procese (numite procese incompatibile) sunt executate pe acelasi procesor, va aparea fenomenul de cache thrashing , care va scadea foarte mult performantele sistemului. Pentru fiecare dintre aceste P perechi de procese incompatibile (i,j) este cunoscuta penalizarea de performanta pei,j, adusa daca cele 2 procese sunt executate pe acelasi procesor. Penalizarea de performanta totala este egala cu suma penalizarilor de performanta pentru fiecare pereche de procese incompatibile care sunt executate pe acelasi procesor.

Determinati penalizarea de performanta totala minima posibila pentru executia celor N procese pe cele K procesoare ale sistemului.

In rezolvarea problemei puteti sa va folositi de urmatoarea particularitate a aplicatiei compusa din cele N procese: Procesele sunt organizate in M grupuri, in functie de tipul prelucrarilor pe care le au de realizat. Grupurile sunt numerotate de la 1 la M. Fiecare grup contine cel mult 8 procese. Un proces poate face parte din mai multe grupuri. Daca 2 procese i si j sunt incompatibile, atunci va exista cel putin un grup X din care fac parte atat procesul i, cat si procesul j. Cele M grupuri sunt organizate intr-o structura arborescenta. Mai exact, exista M-1 perechi de grupuri cu proprietatea ca intre cele 2 grupuri X si Y dintr-o pereche exista referinte reciproce, iar graful format din grupuri ca noduri si perechile de grupuri ca muchii formeaza un arbore (graf conex si fara cicluri). Toate grupurile din care face parte un proces i formeaza un subarbore al arborelui grupurilor (acest lucru se datoreaza faptului ca, in cadrul aplicatiei, este necesar sa se poata ajunge prin intermediul referintelor dintre grupuri, de la orice grup din care face parte procesul i la orice alt grup din care face parte procesul i). Aceasta ultima proprietate este echivalenta cu urmatoarea: daca un proces i face parte din grupurile X si Y, atunci el va face parte din toate grupurile aflate pe drumul unic dintre X si Y.

Date de intrare

Prima linie a fisierului de intrare tproc.in contine numerele intregi M, N si K, separate prin cate un spatiu. Urmatoarele M-1 linii contin cate 2 numere intregi X si Y, separate printr-un spatiu, reprezentand 2 grupuri intre care exista o referinta. Urmatoarele M linii descriu alcatuirea fiecarui grup. A X-a din aceste M linii reprezinta descrierea grupului cu numarul X. Primul numar de pe linie reprezinta numarul T de procese ce fac parte din grupul X. Urmatoarele T numere reprezinta numerele celor T procese. Cele T+1 numere de pe linie sunt separate prin cate un spatiu. Urmatoarea linie contine numarul intreg P de perechi de procese incompatibile. Urmatoarele P linii contin cate 3 numere intregi, i, j si pei,j, separate prin cate un spatiu, reprezentand numerele celor 2 procese incompatibile din cadrul perechii si penalizarea de performanta asociata executiei celor 2 procese pe acelasi procesor.

Date de iesire

In fisierul de iesire tproc.out veti afisa penalizarea totala minima posibila pentru executia celor N procese pe cele K procesoare ale sistemului.

Restrictii

  • 1 ≤ M ≤ 500
  • 1 ≤ N ≤ 500
  • 1 ≤ K ≤ 8
  • Fiecare grup va contine intre 0 si 8 procese (inclusiv).
  • Un proces poate face parte din oricate grupuri (cel putin unul).
  • 0 ≤ P ≤ 3000
  • 0 ≤ pei,j ≤ 1000

Exemplu

tproc.intproc.out
6 9 3
1 3
6 3
4 3
5 3
2 1
7 1 2 3 4 5 7 9
5 1 2 3 5 9
8 1 2 3 4 6 7 8 9
5 2 4 6 7 8
5 2 4 6 7 8
6 1 4 6 7 8 9
22
1 2 703
1 3 485
1 4 384
1 5 216
1 7 670
1 9 410
2 3 789
2 4 977
2 6 210
2 7 856
2 9 610
3 4 780
3 9 453
4 6 149
4 8 528
4 9 85
5 9 949
6 7 754
6 8 457
7 8 204
7 9 827
8 9 700
937
2 10 2
1 2
6 1 2 3 4 5 6
6 1 2 7 8 9 10
12
1 3 1
3 4 1
4 2 1
3 5 1
5 6 1
6 1 1
1 7 1
1 8 1
1 9 1
1 10 1
2 7 1
2 8 1
2 9 1
2 10 1
1

Explicatie

In primul exemplu, o solutie optima a repartizarii celor 9 procese pe cele 3 procesoare este urmatoarea (al i-lea numar din secventa indica pe ce procesor este executat procesul i): 2 2 3 1 3 1 3 2 1.
In al doilea exemplu, o solutie optima a repartizarii celor 10 procese pe cele 2 procesoare este urmatoarea: 1 1 2 1 1 2 2 2 2 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content