Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-03-26 22:10:16.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | proc2.in, proc2.out | Sursă | Algoritmiada 2011, Runda 3 |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | proc2.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
