== include(page="template/taskheader" task_id="proc2") ==
Poveste şi cerinţă...
Avem un calculator cu $N$ procesoare. Există $M$ taskuri care trebuie executate, fiecare având un timp de început $S{~i~}$ şi o durată de procesare $D{~i~}$. Taskurile trebuie executate în ordine cronologică şi fiecare task trebuie executat pe procesorul cu indicele cel mai mic disponibil la momentul de timp $S{~i~}$.
h2. Cerinţă
Trebuie calculat pentru fiecare task procesorul care îl va executa.
h2. Date de intrare
Fişierul de intrare $proc2.in$ ...
Fişierul de intrare $proc2.in$ conţine pe prima linie valorile $N$ şi $M$. Pe următoarele $M$ linii se vor găsi câte două numere $S{~i~}$, $D{~i~}$ separate prin spaţii, cu semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $proc2.out$ ...
În fişierul de ieşire $proc2.out$ trebuie afişate $M$ linii. Pe linia $i$ se va scrie indicele procesorului pe care se execută taskul $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 100.000$
* Pentru orice $i$ între $1$ şi $M$, {$1 ≤ S{~i~} ≤ 2*10^9^$} şi {$1 ≤ S{~i~}+D{~i~} ≤ 2*10^9^$}
* Pentru orice $i$ între $1$ şi $M-1$, {$S{~i~} < S{~i+1~}$}
* Se garantează că fiecare task poate fi executat
* Procesorul care execută taskul $i$ este ocupat la momentele de timp $[S{~i~}, S{~i~} + D{~i~})$
h2. Exemplu
table(example). |_. proc2.in |_. proc2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3
1 2
2 3
3 3
| 1
2
1
|
h3. Explicaţie
...
* La momentul de timp $1$ sunt disponibile procesoarele $1, 2, 3$. Deci taskul $1$ va fi executat de procesorul $1$.
* La momentul de timp $2$ sunt disponibile procesoarele $2, 3$. Deci taskul $2$ va fi executat de procesorul $2$.
* La momentul de timp $3$ sunt disponibile procesoarele $1, 3$. Deci taskul $3$ va fi executat de procesorul $1$.
== include(page="template/taskfooter" task_id="proc2") ==
