498 Scara 3

[•DITzoneC]

Aici puteţi discuta despre problema Scara 3.

[•marius135]

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
 

[•pauldb]

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.

[•c_sebi]

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

[•cos_min]

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

Da.

[•marin]

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)...

[•gabitzish1]

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

[•Tabara]

Eu lucrez cu 2 vectori in care retin: v - nr minim de pasi de a fi ajuns la treapta i si p - pretul minim de a fi ajuns la treapta i in v 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 (cu j dupa i) actualizez v[j]=v+1 si p[j], iar cand v[j]=v+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)...

Si eu luam tot 35 cand in dinamica, la partea du energizant faceam

Cod:

for ( j = 1; j <= suc[i]; ++j )

si actualizam  (i + 2*j ).

Ar trebui sa iti mearga daca faci

Cod:

for ( j = 1; j <= 2*suc[i]; ++j )

si actualizezi i + j.

[•marin]

multumesc mult!

[•Mishu91]

Am o intrebare... pentru exemplul

Cod:

6
1
1 2
2
4 1
1 2

nu 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 

[•shnako]

Am o intrebare... pentru exemplul

Cod:

6
1
1 2
2
4 1
1 2

nu 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.

[•Robybrasov]

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?

[•Mishu91]

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)

[•Robybrasov]

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

[•cvicentiu]

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

[•stocarul]

Vlad, ai scris că:

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

Dar în enunț scrie:

Daca bea q (q ≤ y) decilitri dintr-o astfel de sticla, la urmatorul pas G poate urca pana la 2q trepte

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.

[•APOCALYPTO]

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.

Cod:

struct nod{
    short leg;

    short bani;
};
short H[12001];
vector<nod> G[12001];
queue<short> q;
int N,K,d[12001];
int bani[12001];
short isinq[12001],L;

[•wefgef]

Sunt bune testele.

[•dornescuvlad]

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.

[•pauldb]

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?

[•DraStiK]

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.

[•dornescuvlad]

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  .

[•darkseeker]

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
?

[•skull]

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

[•DorelBarbu]

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?