Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: [10] Branza  (Citit de 1573 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
azotlichid
Echipa infoarena
Nu mai tace
*****

Karma: 50
Deconectat Deconectat

Mesaje: 260



Vezi Profilul
« : 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)
« Ultima modificare: Ianuarie 06, 2007, 11:23:23 de către Mircea Pasoi » Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : Noiembrie 23, 2005, 21:57:39 »

Asta nu merge la a 9-a , ca iti trebuie deque, nu?
Memorat
azotlichid
Echipa infoarena
Nu mai tace
*****

Karma: 50
Deconectat Deconectat

Mesaje: 260



Vezi Profilul
« Răspunde #2 : 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
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines