Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-03-26 22:10:16.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:proc2.in, proc2.outSursăAlgoritmiada 2011, Runda 3
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Proc2

Avem un calculator cu N procesoare. Există M taskuri care trebuie executate, fiecare având un timp de început Si şi o durată de procesare Di. Taskurile trebuie executate în ordine cronologică şi fiecare task trebuie executat pe procesorul cu indicele cel mai mic disponibil la momentul de timp Si.

Cerinţă

Trebuie calculat pentru fiecare task procesorul care îl va executa.

Date de intrare

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 Si, Di separate prin spaţii, cu semnificaţia din enunţ.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ M ≤ 100.000
  • Pentru orice i între 1 şi M, 1 ≤ Si ≤ 2*109 şi 1 ≤ Si+Di ≤ 2*109
  • Pentru orice i între 1 şi M-1, Si < Si+1
  • Se garantează că fiecare task poate fi executat
  • Procesorul care execută taskul i este ocupat la momentele de timp [Si, Si + Di)

Exemplu

proc2.inproc2.out
3 3
1 2
2 3
3 3
1
2
1

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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?