|
Titlul: [10] Branza Scris de: Adrian Vladu din Noiembrie 19, 2005, 17:38:44 Autor: Adrian Vladu
Timp de gandire: 20 min Timp de implementare: 40-50 min Cunostinte de algoritmi: 4 Cunostinte de matematica: 2 Branza Taranul s-a plictisit de munca pe camp si a decis sa isi intemeieze o afacere. In acest sens, si-a deschis o fabrica de branza. In urmatoarele (1 <= N <= 500 000) saptamani, pretul branzei va fluctua, in functie de cerere. Din fericire, taranul cunoaste dinainte (nu se stie de unde) care vor fi preturile in saptamanile ce vor urma. El vrea sa isi minimizeze costurile si sa acopere cerinta de branza. Pentru fiecare saptamana el cunoaste costul C (1 <= C <= 5000) pentru a produce un kg de branza si cantitatea P(1 <= P <= 10000) care va fi cumparata. Taranul poate produce intr-o saptamana orice cantitate de branza. El poate depozita excesul de branza intr-un depozit, dar trebuie sa plateasca S unitati monetare pentru fiecare kg de branza depozitat timp de o saptamana. Branza poate fi depozitata maxim T (1 <= T <= 500 000) saptamani inainte sa se strice. Ajutati taranul sa-si minimizeze costurile. Input Linia 1 : trei numere intregi N, S, T Urmatoarele linii : Ci Pi Output costul minim pt a satisface cerinta de branza Exemplu Intrare 5 10 3 12 1 21 2 27 4 45 5 52 3 Iesire 488 Complexitate O(N) Titlul: Branza Scris de: Mircea Pasoi din Noiembrie 23, 2005, 21:57:39 Asta nu merge la a 9-a , ca iti trebuie deque, nu?
Titlul: Branza Scris de: Adrian Vladu din Noiembrie 24, 2005, 09:46:37 ok..poate am exagerat pt a 9-a... dar la a 10-a sau la 11-12 ca problema usoara merge
|