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 ≤$), 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.
* 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") ==
