Fişierul intrare/ieşire:muncitori.in, muncitori.outSursăAlgoritmiada 2012, Runda 4
AutorAdrian DiaconuAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Muncitori

Cei N muncitori de la Fabrica de Bere au o zi grea astazi, din cauza ca trebuie sa verifice calitatea celor M loturi propuse pentru export. Directorul Fabricii a afisat o lista cu momentele in care ar trebui sa inceapa verificarea fiecarui lot, Ai, cat si durata aproximativa pe care un muncitor o petrece facand respectiva verificare, Bi. Pentru a putea pleca acasa cat mai devreme posibil, muncitorii vor sa faca aceste verificari intr-un mod foarte organizat: vor lua loturile in ordine cronologica dupa momentul de start scris pe lista, fiecarui lot fiindu-i atribuit muncitorul liber care are al K-lea numar de ordine. Odata ce un muncitor incepe verificarea lotului i, el va fi ocupat pentru Bi secunde, fiind liber din nou la momentul Ai + Bi.

Cerinta

Dandu-se N, M, K si cele M perechi A B, sa se determine si sa se afiseze pentru fiecare lot ce muncitor ii va fi asociat.

Date de intrare

Fişierul de intrare muncitori.in va contine pe prima linie numerele N, M si K, cu semnificatiile din enunt. Urmatoarele M linii vor contine cate o pereche Ai Bi, momentul de start si durata pentru verificarea lotului i.

Date de ieşire

În fişierul de ieşire muncitori.out se vor afisa M numere naturale, pe linii separate, al i-lea dintre ele reprezentand muncitorul care realizeaza verificarea cu numarul de ordine i, considerand muncile in ordinea in care se executa(ordonat dupa timpul de incepere al verificarii).

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 100.000
  • 1 ≤ K ≤ N
  • 1 ≤ Ai, Bi ≤ 1.000.000
  • Se garanteaza ca pentru fiecare dintre cele M verificari vor exista cel putin K muncitori disponibil.
  • Pentru 20% din teste N, M ≤ 1.000
  • Pentru alte 20% din teste K = 1.
  • Nu exista doua verificari care sa inceapa la acelasi moment de timp.

Exemplu

muncitori.inmuncitori.out
4 3 1
4 6
5 2
7 3
1
2
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?