== include(page="template/taskheader" task_id="pm2") ==
Poveste şi cerinţă...
La o firmă de software se lucrează la un mare proiect. Proiectul constă în executarea a $N$ faze de dezvoltare, numerotate cu numerele $1, 2, ..., N$. Unele faze pot fi executate în paralel (în acelaşi timp), însă executarea altor faze nu poate fi începută până când nu se finalizează executarea anumitor faze.
h2. Cerinţă
Să se scrie un program care să se determine:
* Timpul minim $t$ în care se poate finaliza executarea proiectului
* Pentru fiecare fază $k$ ( $1 ≤ k ≤ N$ ), momentul de timp {$c{~k~}$} la care poate începe faza $k$ cel mai devreme, respectiv momentul de timp {$d{~k~}$} la care poate începe faza $k$ cel mai târziu, fără a influenţa durata totală de executare a proiectului.
h2. Date de intrare
Fişierul de intrare $pm2.in$ ...
Fişierul de intrare $pm2.in$ conţine:
* pe prima linie, un număr natural $N$, reprezentând numărul fazelor proiectului
* pe a doua linie, $N$ numere naturale, separate prin câte un spaţiu, reprezentând timpul necesar finalizării fiecărei faze
* pe fiecare linie $k$ dintre următoarele $N$ linii, un număr natural {$m{~k~}$} şi un şir a format din {$m{~k~}$} numere naturale: {$a{~1~}$}, {$a{~2~}$}, ..., {$a{~mk~}$}, cele {$m{~k~}$} $+ 1$ numere din linie fiind separate prin câte un spaţiu, {$m{~k~}$} reprezentând numărul de faze ce trebuie finalizate înaintea începerii fazei k, iar numerele din şirul a reprezentând numerele de ordine ale fazelor ce trebuie finalizate înaintea începerii fazei k
h2. Date de ieşire
În fişierul de ieşire $pm2.out$ ...
Fişierul de ieşire $pm2.out$ va conţine $N+1$ linii. Pe prima linie se va scrie numărul natural $t$, iar pe fiecare linie $k$ dintre următoarele $N$ linii, se vor scrie cele două numere naturale {$c{~k~}$} şi {$d{~k~}$}, separate prin câte un spaţiu.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 ≤ N ≤ 100$
* Timpul necesar finalizării executării oricărei faze nu va depăşi $1.000.000$
* Se consideră că executarea proiectului începe la momentul de timp $0$
* Nu vor exista dependenţe circulare (proiectul întotdeauna se poate finaliza)
* Pentru rezolvarea primei cerinţe se acordă 40% din punctaj, iar pentru a doua cerinţă se acordă câte 30% din punctaj pentru prima, respectiv a doua valoare.
h2. Exemplu
table(example). |_. pm2.in |_. pm2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
2 3 5 3 3 3 2
0
0
1 2
1 1
1 1
3 3 4 5
1 3
| 11
0 3
0 0
3 3
2 5
2 5
8 8
8 9
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="pm2") ==
