1375 Lumanari

[•savim]

Aici puteti discuta despre problema Lumanari.

[•superman_01]

in timpul concursului nu am reusit sa scot decat 60 de pct cu incorect,dar nu inteleg ce am gresit.Eu am facut suma tuturor inaltimilor si am tinut un contor cu nr de lumanari>0 (acestea fiind nr maxim de zile).Dupa am cautat un nr n*(n+1) /2 maxim astfel incat sa fie cat mai aproape de suma inaltimilor.Daca aceste depasea contorul ,afisam contorul. Eu nu gasesc niciun contra-exemplu.Poate cineva sa  imi zica ce am gresit?

[•savim]

Pentru cei care intampina probleme la Lumanari - incercati urmatoarele teste:

Cod:

6
2 2 2 2 2 2
Raspunsul e 4

6
1 1 1 4 5 6
Raspunsul e 5

[•superman_01]

mie imi merge pe ambele teste si totusi iau 60   

Alte teste mai dificile nu sunt ?

[•PlayLikeNeverB4]

Cod:

6
6 1 1 1 1 1
Raspunsul e 3

[•superman_01]

Mi-a iesit pana la urma.Dar consider ca algoritmul meu nu este corect si cred ca iau cam mult(100) cu niste bulaneli.

[•proflaurian]

@Cristian Avramescu

Banuiesc ca ai aceeasi greseala pe care am avut-o si eu. Lumanarile de inaltime 0 care trebuie ignorate ( si eu tot 60 de puncte am avut)

[•deneo]

Cautare binara

[•superman_01]

@Panaete Adrian
Eu am avut probleme la testul dat Marcus.Dar totusi solutia mea nu este optima am unele teste pe care pica. oricum o sa incerc sa  o fac si cu cautare binara.

[•ctlin04]

Totusi care este solutia oficiala la problema asta? Eu am o solutie care intra in timp, dar care este teoretic gresita, de ce zic teoretic pentru ca practic ia incorect doar pe ultimul test. O alta solutie , care sunt sigur ca este corecta, are complexitatea N*log^2 N si nu intra in timp. 

[•superman_01]

Eu am sortat vectorul inaltimilor descrescator(dupa ce am eleminat zerourile) si dupa aceea am cautat binar nr de zile.

[•ctlin04]

Eu la fel am sortat vectorul si apoi am cautat binar numarul de zile, doar ca pentru un numar de zile fixat, nu stiu cum sa vad dintr-o parcurgere daca se poate indeplini sau nu, eu fac asta in N*logN, de aici si apare log^2N.

[•superman_01]

pai in functia de cautare binara verifici daca poti din fiecare zi sa scazi nr maxim de zile.
Pt exemplul dat :
tu o sa ai
6 5 4 3 1 1 si ca sa poti sa ai 5 zile trebuie ca in ziua 5 sa ai minim 5 lumanari de inaltime minim 1 .deci verifici cu un rest daca din ziua x(cu x incepand de la 1) daca  poti sa scazi 5,respectiv 4 si tot asa(practic verifici daca ai nevoie de lumanari mai inalte ca sa faci ziua aia).daca el e 0 atunci inseamna ca poti sa gasesti un numar mai mare de zile. Cat despre ultimul test am vazut ca mai multe lume are probleme cu el. 

[•RaduGabriel2012]

Care-i problema la ultimul test ?  Ma chinui de o gramada de timp si nu-mi dau seama ce ar putea fi

[•misino]

Nu puteti sa dati un test asemanator cu ultimul pe care sa nu-l trecem sa ne dam seama ce-am gresit?

[•repp4radu]

7
3 3 3 3 3 3 3

ans: 6

[•misino]

Multumesc!
Acu trebuie ssa vad de ce imi greseste.

[•rares96cheseli]

cred ca ar trebuie putin modifcate testele deoarece daca numar lumanarile nenule din sirul initial si afisez acel numar iau 60p, ceea ce nu mi se pare prea ok.

[•robertstreche]

un test mai mare puteti pune?