Fişierul intrare/ieşire:sant.in, sant.outSursă.campion 2003
AutorNistor Eugen MotAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sant

Pentru a sapa un sant de lungime S, apelam la o firma de constructii care ne pune la dispozitie muncitori de diverse categorii (in total C categorii notate 1, 2, ..., C). Un muncitor de categorie superioara munceste mai mult si mai bine, dar cere si un salariu mai mare. Vrem sa terminam lucrarea intr-o singura zi, asa ca ne intereseaza pentru fiecare categorie care e salariul si cati metri sapa pe zi un muncitor din categoria respectiva. In plus vrem sa angajam exact N muncitori (avem N locuri la masa!). Se mai stie ca pentru fiecare categorie exista un numar suficient de mare de muncitori si un muncitor nu se opreste pana nu sapa lungimea corespunzatoare categoriei sale.

Cerinta

Gasiti posibilitatea de a angaja N muncitori de diverse categorii care sa sape exact S metri intr-o zi si sa poata fi platiti cu suma cea mai mica posibila.

Date de intrare

Pe prima linie a fisierului de intrare sant.in sunt scrise numerele naturale S, N si C, (lungimea santului, numarul de muncitori pe care vrem sa-i angajam si numarul de categorii) separate prin cate un spatiu. Pe urmatoarele C linii sunt cate doua numere naturale Li si Pi (i= 1, 2, ..., C) reprezentand lungimea santului sapat si plata ceruta pentru o zi, de un muncitor de categoria i.

Date de iesire

Prima linie a fisierului sant.out va contine suma minima care poate fi platita unui numar de N muncitori care sapa exact S metri intr-o zi sau cifra 0 daca nu exista solutie. Daca exista solutie, urmatoarea linie va contine un sir de N numere ordonate crescator, reprezentand categoriile muncitorilor angajati. Daca sunt mai multe solutii se va alege solutia cea mai mica din punct de vedere lexicografic (pentru cine a uitat, un exemplu: conform ordinei lexicografice sirul 1 1 1 2 3 3 este mai mic decat sirul 1 1 2 2 2 3).

Restrictii

  • 1N100
  • 1S1000
  • 1C20
  • 1Li, Pi100

Exemplu

sant.insant.out
15 5 4
1 1
2 3
3 7
5 10
27
1 2 2 4 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content