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

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


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
16MB / 1MB

Meşterul Vasile are o firmă de microprocesoare. Pe 1 ianuarie el îşi planifică activitatea pentru următoarele n zile. Analizând graficul de producţie pentru cele n zile, Vasile ştie că în ziua i firma sa poate produce cel mult pi microprocesoare, costul de producţie al unui microprocesor fiind cpi (1in). Analizând situaţia comenzilor, Vasile ştie că în ziua i el trebuie să livreze exact nri microprocesoare (1in). Microprocesoarele care nu sunt livrate pot fi trimise la depozit pentru a fi utilizate ulterior. În noaptea dintre zilele i şi i + 1 pot fi depozitate cel mult di microprocesoare, costul depozitării unui microprocesor fiind cdi (1i < n).

Cerinţă

Scrieţi un program care să determine care este suma minimă pe care meşterul Vasile trebuie să o cheltuiască pentru producţie şi depozitare astfel încât să satisfacă toate comenzile pentru cele n zile.

Date de intrare

Fişierul de intrare micro.in conţine pe prima linie numărul natural n. Pe următoarele n linii se află informaţii despre producţie şi comenzi. Mai exact, pe cea de a i-a linie dintre cele n se află trei numere naturale separate prin spaţii: pi cpi nri (1in). Pe următoarele n - 1 linii se află informaţii despre depozitare. Mai exact, pe linia i dintre cele n - 1 (1in - 1) se află două numere naturale separate prin spaţiu di cdi.

Date de ieşire

Fişierul de ieşire micro.out va conţine o singură linie pe care va fi scris un singur număr întreg: suma minimă necesară pentru satisfacerea tuturor comenzilor sau valoarea -1 dacă acest lucru nu este posibil.

Restricţii

1n100.000
0pi, cpi, nri1.000.000.000, pentru 1in
0di, cdi1.000.000.000, pentru 1in - 1
Numărul din fişierul de ieşire se încadrează în tipul întreg pe 64 biţi cu semn

Exemple

micro.inmicro.outExplicaţii
3 10 4 1 2 2 6 11 10 8 7 3 3 5 116 În prima zi pot fi produse maxim 10 microprocesoare, la 4 lei microprocesorul şi trebuie să fie livrat un singur microprocesor. Cost pentru ziua 1: 4 lei. Peste noapte pot fi stocate doar 7 microprocesoare, la costul de 3 lei bucata.
A doua zi sunt produse două microprocesoare cu 2 lei bucata şi trebuie să fie livrate şase. Vom livra cele două microprocesoare produse + 4 din depozit (stocate din prima zi). Cost pentru ziua 2: 2 * 2 + (4 + 3) * 4 = 32.
A treia zi pot fi produse maxim 11 microprocesoare la costul de 10 lei bucata şi trebuie să fie livrate 8 microprocesoare. Este preferabil să livrăm 8 procesoare produse în ziua 3 cu 10 lei bucata adică în total 80 lei. Cost total: 4 + 32 + 80 = 116.

autor: Prof. Emanuela Cerchez
propunător: Vlad Manea
Facultatea de Informatică Iași
vlad.c.manea@gmail.com
Articole recomandate
Probleme recomandate
De la FII Competition 2011: lipsa, reducere, viena, sir9, sablon2, fibgcd, acoperire, razboi, safeu, centrala, benzina2, bradut2, capra, agendatelefonica, cds, wg
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Software recomandat
surse trimise | ajutor