.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » sant

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
sant


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
15 MB/1 MB

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

  • 1 <= S <= 100
  • 1 <= N <= 50
  • 1 <= C <= 10
  • 1 <= Li <= 50
  • 1 <= Pi <= 100

Exemplu

sant.in sant.out
15 5 4
1 1
2 3
3 7
5 10
27
1 2 2 4 4

prof. Mot Nistor
Colegiul National "N.Balcescu" - Braila
Contact:emotz_ro@yahoo.co.uk

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2003: newcomp, rima, algebra, turn1, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, stop, hanoi, lift, pic, sms, fibo, bac, parc, circular, logn, lex, joc7, cuburi1, mobile, pattern, oras, produs, mutare, viteza, concurs2, furnici, homeless, subsir
De acelaşi autor: cursa, insule, termen, div, mese, hperm, zmeu, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, parc, circular, mobile, pattern, mutare, concurs2, soricel1, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, tort1, triunghi4, bile6, zmax
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor