029 Lapte

[•fluffy]

Aici puteţi discuta despre problema Lapte.

[•ParrAzitU]

 vroiam sa intreb, cam la ce complexitate se asteapta de la lapte..
eu am un O(n^3 lg n) si iau tle pe toate...

sunt toate testele asa mari si inumane ?  

[•greco]

n^3 log n se asteapta... stiu de la autor  

Da vezi ca merge greedy in n log n daca te dai batut cu dinamica.  

[•ParrAzitU]

well, mai am putin si ma dau batut cu dinamica.
Am o cautare binara si inauntru un for dupa n si un for dupa T imbricate..
Si iau tle pe 6 teste... Ma mir ca dinamica ce am facuto merge cam la bulan.. Ma asteptam sa iau WA.. da nici vorba..
numi dau seama ce are..
Oricum cred ca ma apuc de greedy  

[•tm_radu]

Cam cum s-ar rezolva problema in O(n*log n)? ca nu imi vine nici o idee in minte?

[•pocaitu]

    Ma chinui si eu de ceva vreme la pb asta si nu pot sa gasesc formula de recurenta. Nu da un hint cineva ? ? Pentru solutia O(N^3lgn)

Later Edit: pana la urma nu da nimeni un hint ? N-am nici o idee ce sa caut binar  Confused

editat de moderator: nu mai posta de 2 ori consecutiv, mai ales daca este despre aceiasi idee
        ce puteam sa fac , daca nu raspundea nimeni 

[•astronomy]

Cauti binar timpul minim, iar pentru un timp minim fixat faci dinamica.

[•peanutz]

Cred ca o idee de recurenta ar fi: v[ i ] = numarul maxim de litri de lapte B beuti, pentru i litri de lapte A... si faci o chestie gen rucsac... banuiesc ca nu e solutie unica(ar fi absurd).. totusi iau 0, probabil de la implementare, revin mai tarziu cu niste teste sa vad cat va da tmin... in principiu, cum e recurenta?

[•pauldb]

Ideea ta e buna, doar ca ti-ar mai trebui o dimensiune ca sa-ti faci reconstituirea mai usoara. Ar fi mai frumos daca nu s-ar posta recurenta aici. Daca in continuare ai probleme, da un PM. 

[•cosmin79]

Salut.Am facut si eu cautare binara+verificare prin programare dinamica la problema asta.Iau 60 pct cu wa.As avea cateva intrebari daca binevoieste cineva sa-mi raspunda.
1)Orice solutie se considera a fi corecta?
2)Daca s-a asigurat nr minim de L de litri de lapte de tip A si B pt un anumit timp T si T e minim cu aceasta proprietate, se prespune ca prietenii lui Haralambie trebuie sa bea in continuare lapte pe tot parcursul lui T sau pot sa nu bea deloc?
3)eventuale alte cazuri particulare
Mersi anticipat! 

[•pauldb]

1. Da.

2. Se presupune ca prietenii beau tot timpul T, dar este important ca ei sa bea cel putin L litri de lapte A si B (adica daca depasesc L e ok).

3. Nu cred ca exista cazuri particulare. Incearca sa-ti verifici solutia pe mai multe teste, poti posta eventual unele mai mari daca nu te descurci.

[•RazvanS]

Pentru testul:

3 20
1 1
3 5
1 6

ce trebuie sa dea?

later edit: Ma derutase postul precedent. I've figured it out.

[•Bit_Master]

Dar daca unul bea tot timpul, chiar daca spre sfarsit bea fara sa apuce sa termine, e corect?
Adik de exemplu dupa ce a baut necesarul, mai are timp t = 1 min. Dar bea un litru de lapte A in 1 min si lapte B in 2 min, poate sa inceapa sa bea lapte B (daca are timp)? Dar daca bea A in 2 min si B in 2 min (sau mai mult)?

[•pauldb]

Trebuie sa bea un numar intreg de litri de lapte din fiecare tip.

[•siminescu]

va rog... cum as putea sa primesc datele de la testul 4 ? citisem parca undeva ca trebuie sa dau mesaj privat pt asa ceva dar nu stiu cui trebuie sa dau. multumesc!

[•PetcuIoan]

Ce a patit evaluatorul?
Iau tle pe o sursa care intra in timp...
http://www.infoarena.ro/job_detail/944021
http://www.infoarena.ro/job_detail/687589

[•freak93]

O sa mearga mai greu azi cat instalam o chestie.

[•DorelBarbu]

Are cineva un test mai consistent, va rog?