491 Lacusta

[•DITzoneC]

Aici puteţi discuta despre problema Lacusta.

[•devilkind]

ati putea pune si o explicatie. cum se obtine suma 28? nu reusesc sa inteleg cum se fac acele deplasari. Din ce am inteles eu la o deplasare ma mut pe o linie invecinata in orice coloana, dar asa as putea obtine suma 14 si ar fi mai mica decat 28.

[•marius135]

am impresia ca se misca asa
cost 3 +
1 1 - > 1 3  + 5
1 3 - > 2 3  + 3
2 3 - > 2 2  + 6
2 2 - > 3 2   + 3
3 2 - > 3 3  + 3
3 3  -> 4 3  + 3
4 3  ->  4  5 + 2
= 28
sper sa te ajute

[•skyel]

idee e ca esti obligat ca pe fiecare linie sa "calci" de 2 ori, si de aceea sunt 2m sarituri si nu poti pur si simplu sa te duci
1-1
1-5
5-5
ca sa obtii 14
LE: in enuntu initial al problemei era si explicatia, si cred ca nu s-ar supara nimeni daca s-ar adauga si in arhiva

[•Florian]

LE: in enuntu initial al problemei era si explicatia, si cred ca nu s-ar supara nimeni daca s-ar adauga si in arhiva

S-a rezolvat! 

[•supernova]

Deplasarea se face intotdeauna in ordinea saritura-pas, sau pot avea intai pasul si apoi saritura?

[•skyel]

La fiecare deplasare se executa un salt pe orizontala si un pas pe verticala.

deci cam da

[•supernova]

Nu reiese de aici ordinea. Deci pot avea 2 salturi consecutive sau 2 pasi consecutivi (care fac parte din doua deplasari diferite)?

[•Dastas]

O deplasare = salt + pas. Asta inseamna ca o sa ai o insiruire de miscari salt + pas + salt + pas + salt + pas + ...

Nu poti avea doua salturi sau doi pasi consecutivi (iar daca fac parte din doua deplasari diferite nu mai sunt consecutive... n-am inteles ce ai vrut sa zici cu asta)

[•BigMazilu]

In file included from /usr/include/c++/4.2/backward/fstream.h:31,
                 from user.cpp:1:
Asta ce eroare mai este???

[•stef2n]

Ce ai selectat tu este doar locul unde apare problema. Nu este o eroare, ci un warning:

#warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.

Ti se sugereaza sa folosesti headerul <fstream> in loc de <fstream.h> pentru a scrie cod in conformitate cu noile standarde C++.

[•BigMazilu]

Se intampa ceva ciudat .. Cand initializez matricea A[20][20] imi da evaluare completa : 0 puncte iar la A[250][250], asa cum ar trebui sa fie matricea imi da eroare de compilare...dar exact cu acelasi mesaj de eroare in ambele cauri (vb  de mesajul care l-am postat mai sus)...PS Acasa merge problema ...rezultatul este 28 pentru exemplul care este pe infoarena..Am rezolvat cu programare dinamica

[•stef2n]

Eroarea de compilare o primesti din cauza ca nu sunt declarate cout si endl. Incearca sa pui la inceput linia

Cod:

using namespace std;

[•jupanubv92]

Ce ma dispera problema daca imi declar doua matrice de 250 iau memory limit exces pe ultimu test iar daca pun 249 iau incorect pe primu test ... asta inseamna ca primu test este de 250/250 si aveti vreun sfat pentru mine ce as putea sa fac ?

LE: Am reusit sa o rezolv .. de 100 chestia era ca trebuia sa imi declar toate variabile unsigned int ca sa scot memoria la mine erau de tip int scz ptr mesajul de dinainte.  Iarasi ma luat gura pe dinainte si mam apucat sa postez pe forum cu toate ca am promis ca nu mai fac asa ceva ...

[•MciprianM]

int si unsigned int ocupa tot atata memorie

[•jupanubv92]

Nu cred pentru ca aveam doua matrice de 250 /250 si memoria era la maxim luam si Memory limit exces pe ultimu test iar dupa ce am pus unsigned int a scazut memoria de la 654 la 420 deci cred ca e diferenta astfel nu imi explic de ce a fost asa mare diferenta dupa ce am pus unsigned int.

[•stocarul]

Am creeat doua tablouri asa:

unsigned char a[252][252];   //252*252*1/1024=62KB
int b[252][252];   //252*252*4/1024=248KB

62+248+cateva variabile int...... sigur e mai putin de 600KB...
De ce Memory limit exces pe primul si ultimul test? Calculez eu cumva memoria folosita gresit?

[•Bogdan_tmm]

Incearca sa pui unsigned short

[•stocarul]

Incearca sa pui unsigned short

Tot imi da "Memory limit exces" pe primul si pe ultimul test....insa nu inteleg de ce.....pt ca dupa calculele mele, eu nu folosesc 600KB de memorie .....

LE: Scz....n-am fost atent...acum cand am modificat cu unsigned short imi da "Time limit exceeded." la primul si ultimul test )
Cum se rezolva problema?....eu am facut-o in o(m*n^2)......

LE: Am reusit pana la urma 100 in (M*2*n)  ... si am vazut k acum imi incape o matrice de tip char si una de tip int.....asta e cam ciudat....

[•zalman]

Stie cineva ce au mai special testele 5 si 9? La alea iau incorect...de ce?

[•c_e_manu]

nu prea e nimic special 

cel putin eu nu am intalnit problema asta... mai verifica o data implementarea... poate nu iti gasesti corect valorile alea minime 

[•alexandru92]

Imi zice si mie cineva ce este gresit la metoda asta de rezolvare, sa luam exepmlul din problema :
4 5
3 4 5 7 9
6 6 3 4 4
6 3 3 9 6
6 5 3 8 2
initial s=a[1][1]+a[n][m],adica s=5;
apoi incep pe linia n calculez suma de pe fiecare pozitie, adun nr de deasupra, execptand  pozitia m si linia devide : 12 8 6 17 x(unde se afla lacusta),
selectez minimul 6 si apoi pun lacusta pe el, apoi restaurez linia    si urc pe linia n-1.
fac dinou suma  si linia devine 12 9 x 13 10 selectez minimul si tot asa pana ce  linia ==1 unde  ma opresc
La exemplu suma devine  28
Dar pentru exemplu 
5 5
9 1 9 8 8
6 6 9 4 4
1 2 7 9 6
2 6 3 3 8
5 8 2 3 8
Programul meu afiseaza  45 in loc de 42

[•Florian]

Cod:

5 5
9 1 9 8 8
6 6 9 4 4
1 2 7 9 6
2 6 3 3 8
5 8 2 3 8 

Pt exemplul asta, drumul optim este: (1,1) -> (1,2) -> (2,2) -> (2,5) -> (3,5) -> (3,1) -> (4,1) -> (4,3) -> (5,3) -> (5,5). Insumand, 9+1+6+4+6+1+2+3+2+8 = 42. Problema se rezolva cu programare dinamica. Ce ai facut tu se numeste greedy, si nu da solutia optima tot timpul, desi s-ar putea sa prinzi ceva puncte. Spor!

[•alexandru92]

Multumesc,da  am  prins  10 pct si la programare dinamica trebuie sa mai lucrez ca nu inteleg nimic din ea , din pacate

[•moonbeam]

Stie cineva un site in care este explicata ( pe intelesul oricui )dinamica?