infoarena

Aici puteţi discuta despre problema Scara 3 (http://infoarena.ro/problema/scara3).

o mica problema pe care am avut-o si poate va fi de folos altora:
cele n trepte sunt numerotate de la 0 la n-1 nu de la 1 la n
 :fighting:

Nu e adevarat. Cele N trepte sunt numerotate de la 1 la N. Poate ca te refereai la faptul ca pleci din afara scarii. Asta e altceva.

Dintr-o sticla cu apa se poate bea orice cantitate k <= x, si apoi se pot urca k trepte cu un singur pas?

Da.

Eu lucrez cu 2 vectori in care retin: v[ i ] - nr minim de pasi de a fi ajuns la treapta i si p[ i ] - pretul minim de a fi ajuns la treapta i in v[ i ] pasi.
Parcurg i de la 1 la n si de pe scara i analizez cele 3 cazuri de a actualiza v si p pentru scarile de dupa i (beau apa, beau energizanta, urc normal). cand v[ j ]>v[ i ] (cu j dupa i) actualizez v[ j ]=v[ i ]+1 si p[ j ], iar cand v[ j ]=v[ i ]+1 actualizez p[ j ]. Plec cu v[1]=1 si p[1]=0 si afisez v[n] si p[n].
Unde gresesc ? (iau 35 p, in rest WA)...

Gresesti la cazul in care bea energizanta... si eu luam 35 din cauza asta. Ai grija cat urci si cat platesti.

Si eu luam tot 35 cand in dinamica, la partea du energizant faceam
si actualizam  (i + 2*j ).

Ar trebui sa iti mearga daca faci
si actualizezi i + j.

multumesc mult!

Am o intrebare... pentru exemplulnu ar putea bea pe prima treapta bautura energizanta, si sa ajunga pe treapta 4, iar apoi sa bea din nou o bautura energizanta si sa ajunga pe treapta 6, din doua sarituri, dar cu costul 1+2 = 3  :?

Trebuie sa sara 2q trepte daca bea suc, deci doar numere pare. Dar 4-1=3 deci nu se poate.

pentru acelasi exemplu, daca bea bautura energizanta pe prima treapta, poate sa mearga 2*2=4 trepte, adica ajunge de pe 1 pe 5, si de acolo mai da un pas fara sa bea nimic si ajunge in 6. adica 2 pasi si 2 lei. de ce nu e corect?

La care se adauga pasul de la 0 la 1. Pentru ca el se afla pe podea (treapta 0) :)

o..  :D pardon.. ma gandeam ca incepe din 1

Am trimis vre-o 7 surse si punctajul lor mi-a variat de la 35 la 0 si iar la 35. 2 dintre ele le-am rescris de la 0.

Nu inteleg unde gresesc la dinamica. Fac aproximativ acelasi lucru cu 2 vectori v si c, primul tinand numarul de pasi, al doilea costul. Actualizez pe rand in cazul in care o ia inainte fara sa bea nimic, o ia inainte doar cu apa, o ia inainte cu suc. (pt fiecare decilitru in plus consumat)
Afisez intr-un final v[n] si c[n].

pt a nu da toata solutia, scriu doar ce actualizez la vectori in cele 3 cazuri:
sunt conditii pe acolo in caz in care am mai ajuns sa modific o data pozitia respectiva in vector, dar e cam toata solutia.

v[i+1]=v[i ]+1, c[i+1]=c[i ];  //cand nu avem nimic
v[i+j]=v[i ]+1, c[i+j]=c[i ];   //cand avem apa (j decilitri) nu ne costa nimic
v[i+2*j]=v[i ]+1, c[i+2*j]=c[i ]+j;   //cand avem suc (j decilitri) cand bem suc ne costa exact cati decilitri am baut si avansam cu un singur pas 2*j trepte :-?

Daca e prea mult info le sterg insa chiar nu inteleg, am priceput eu gresit problema? Testele mele merg bine.

Edit: Cred ca m-am prins unde greseam la suc, i'll try one more tonight :D

Vlad, ai scris că:
Dar în enunț scrie:
Nu zice nicăieri că trebuie să urce un număr par de trepte.
Plus că informația nu ai verificato ... Dacă ai fi trimis o sursă care să urce câte 2q trepte, ai fi văzut că nu obțineai 100 pct.

Sigur este buna limita lui N la problema? Vreau sa spun ca daca declar vectorii a[1205] iau 65 de puncte si daca ii declar a[12000] iau 80 de puncte.
Si nu se poate lua 100 de pucnte cu bellman ford?
La mine depaseste limita de memorie.

Sunt bune testele.

Pentru primul exemplu, de ce nu ar merge asa?
Sare de pe scara 1 pe scara 4 (cu apa de pe scara 1) pas = 2 , cost = 0
Sare de pe scara 4 pe scara 6 (cu energizantul de pe scara 4) pas = 3, cost = 2 / 2 = 1

nrpasi = 3, cost = 1.

Din cate inteleg din enunt, daca bei apa de pe scara 1 nu poti urca decat doua trepte, deci ai ajunge pe treapta 3. Vad ca ai luat 100 intre timp, asta era?

Pai in primul rand incepe de la baza ( cum ar veni - scara 0 ).

Deci de pe 0 pe 1, un pas, cost 0.
Apoi de pe 1 merge pe 5 folosind bautura energizanta, al doieal pas - cost 2.
Iar in final merge de pe 5 pe 6, inca un pas si cost tot 0.

Deci 3 pasi si costul 2.

Mersi.
Eu ma gandeam tot timpul la termenul 'sare' peste x scari in loc sa ma gandesc la 'urca' x scari (sare x - 1 scari intre a si b).
De aceea greseam acolo, ca nu poate ajunge de pe 1 direct pe 4 cum ziceam eu (ar insemna sa sara 2 scari intre ele, dar el nu poate SARI peste 2 scari ca sa ajunga pe 4, ci doar urca 2 scari si sa ajunga pe 3)
I'm such a  ](*,).

Imi poate spune cineva cat ii da pentru testul :
120 10 2 1 37 1 40 5 60 4 78 19 31 9 12 14 63 1 19 17 76 16 20 92 15 25 7 105 13 102 13 50 10 73 9 61 11 13 7 14 11 53 8 63 6 96 4 20 7 77 3 60 10 69 1 87 5 51 6 42 9 67 5
?

20 31

120 10 2 1 37 1 40 5 60 4 78 19 31 9 12 14 63 1 19 17 76 16 20 92 15 25 7 105 13 102 13 50 10 73 9 61 11 13 7 14 11 53 8 63 6 96 4 20 7 77 3 60 10 69 1 87 5 51 6 42 9 67 5

E o chestie ciudata. Sursa mea ia 100 pe Infoarena. Dar testul de mai sus este ultimul test de pe .Campion, la aceeasi problema.  Raspunsul considerat corect de Infoarena este: 20 31. Pe .Campion cel considerat corect este 20 38. Pana la urma cum sta treaba? Implementarea mea aici este o dinamica inainte. Solutia oficiala a problemei presupunea crearea unui graf si aplicarea algoritmului lui Dijkstra pe el, asta ca fapt divers, fiind din punctul meu de vedere irelevant deoarece o implementare corespunzatoare a uneia din cele doua solutii trebuie sa dea rezultatul corect.

Deci, cine greseste, .Campion sau Infoarena? :-?

eu am incercat sa fac problema aceasta cu un Bellman Ford...initial am tras muchii orientate intre toate scarile (i, i + 1, cu 1 <= i < N)...dupa am mai tras muchii din scarile cu apa/energizant de cost 1 si un pret corespunzator...stiu ca folosesc mult memorie, dar problema e ca pe foarte multe teste imi da incorect...daca a folosit cineva aceeasi ideea , dati-mi un hint va rog unde as pute gresi :-s

Daca cineva poate sa-mi ajuta aici: http://www.infoarena.ro/job_detail/1360537
Primesc numai 85 puncte din cauza timpului :( aici este sursa: http://www.infoarena.ro/job_detail/1360537?action=view-source
Am incercat sa rezolv problema folosind metoda dinamica, iar cred ca am prea multe "for"-uri, si de aceea e prea mult timp pentru compilare. Idee?

Am si eu aceeasi problema iau 85 de puncte cu TLE pe 3 teste imi puteti da un hint cum sa optimizez(am incercat dinamica)

http://www.infoarena.ro/job_detail/1636992?action=view-source