491 Lacusta

[•Mishu91]

Acilea

[•alexandru92]

Se poate afisa testul 1 sau testul 10?....ca deja turbez  ...am incercat programul meu pe toate testele de la oji 2005 si afiseaza rezultatul corect  si se incadreaza in timp.....

[•DraStiK]

ce primesti? WA, TLE sau KBS?

pentru kbs rezolvi daca iti declari matricile de tip short pentru a intra in memorie

[•Florian]

Vezi ca ai nevoie doar de ultimile doua linii, nu de toata matricea [ la dinamica ]. Deci, retine doar ultimile doua linii si o sa intre in memorie. Am impresia ca daca declari short matricea de la dinamica, nu o sa iti dea raspunsuri corecte [ pt ca depasesti domeniul de valori  - short e pe 8 biti (nu?) ] Spor!

[•wefgef]

In gcc short este pe 16 biti.

[•alexandru92]

nu, imi afiseaza  Incorect ... assta ma deranzeaza.
Eu folosesc o matrice de tip int :d...

[•DraStiK]

In gcc short este pe 16 biti.

cred ca si in borland short e tot 16 biti, ca doar char e pe 8 biti

[•alexandru92]

Am gasit  greseala, la mine  a[n][m] era doar de 101X101, in loc de 251X251 .
Dar e un lucru ciudat folosind  functiile din stdio.h ...nu imi aparea KBS11, ci  Incorect si la un moment dat Wa. Dar daca folosesc functiile din fstream , imi apare. Imi explica si mie cineva de ce se intampla acest lucru?
@Marcu Florian  pentru a genera matrice la dinamica n-ai nevoie decat de o varibila, nu de o matrice , sau un vector

[•Florian]

@Marcu Florian  pentru a genera matrice la dinamica n-ai nevoie decat de o varibila, nu de o matrice , sau un vector

Cred totusi ca ai nevoie de cel putin patru variabile. ( doua minime pt linia curenta si inca doua minime pt linia anteriora. Si probabil si pozitiile lor (coloanele), deci inca 4 = > 8 variabile) Gresesc?

[•alexandru92]

Pai  ai nevoie de  2 varibile pentru  minimile de pe linia anterioara +pozitia "celui mai mic minim " + alte 2 minime pentru linia curenta + inca  o varibila pentru pozitia "celui mai mic minim ", si o varibila pentru construirea drumului curent => 7 varibile
[later]:.....am uitat si  un minim pentru ultima linie, da vin 8

[•Necro]

sal,dati-mi si mie un sfat..ce trebuie sa fac...treb sa generez toate posibilitatile unui drum,iau din marginea dreapta a matricii si incerc sa gasesc minimele pentru orice drum pe care l-a luat...cum fac asta?

[•Florian]

Ce spui tu se numeste backtracking, si nu ti-ar intra in timp sub nicio forma. Problema se rezolva prin programare dinamica. Daca nu stii programare dinamica, iti recomand niste probleme clasice ( a se citi "mai usoare"), precum subsir crescator maximal (incearca mai intai de 70 de puncte), cel mai lung subsir comun, suma in triunghi, etc. Ca sa vezi rezolvarea la problema asta, vezi ca exista si un articol cu solutii in arhiva OJI 2005, din sectiunea Downloads. Spor! 

[•Necro]

mersi...la prog dinamica am inteles cum e treaba la problema cu monede, sau la energii...faci programu sa compuna ceva din ce ai aflat pe parcurs...dar nu vad cum poti aplica aici acelasi principiu

[•Florian]

Notezi cu b[ i ][j] - cel mai scurt drum ca sa ajungi pe pozitia (i,j). Evident, rezultatul va fi in b[m][n]. Acum, trebuie sa te gandesti cum poti ajunge in pozitia (i,j). Evident, sunt mai multe variante, asa ca trebuie sa alegi minimul. Spor!

[•Necro]

e ok sa fac suma minima dintre configuratii de genu asta , aplicate pe toate liniile si coloanele?

0 0 0 0           0 0 0 0
0 0 0 *   sau   0 * 0 0
0 0 0 *           0 * * *
 
0 0 0 0         0 0 0 0
0 0 * 0  sau  * 0 0 0
0 0 * *          * * * 

[•Florian]

e ok sa fac suma minima dintre configuratii de genu asta , aplicate pe toate liniile si coloanele?

Nu. Citeste solutia oficiala si sa o sa intelegi. 

[•Bit_Master]

Am si eu o intrebare...
Pentru datele de intrare:
2 2
1 2
3 4

Ce raspuns e? Mie-mi pare imposibil pt ca nu ai voie sa faci un pas direct pe campul final (trebuie sa termini cu un salt), si de asemenea trebuie sa si incepi cu un salt...

[•wscsprint3r]

am si eu o problema...un singur test imi da incorect si nu am idee de ce. Nu are nimeni testele ?

[•skull]

am si eu o problema...un singur test imi da incorect si nu am idee de ce. Nu are nimeni testele ?

Testele nu se fac publice din cate stiu eu. 

[•SpiderMan]

I-ale de la Downloads, sectiunea OJI 2005.
[LE] Skull, daca problema s-a dat la un concurs gen olimpiada, poti sa iei testele pentru ca sunt oficiale .

[•coddo]

sunt tare ciudate testele astea. Am facut tot felul de incercari din cauza ca primeam la ultimul test si la primul test MLE sau Signal 11.
Daca declarati cele 2 matrici ca short de 257x257 si restul variabilelor ca int, o sa functioneze bine

[•PlayLikeNeverB4]

Teoretic nu ar trebui sa functioneze asa pentru ca ar putea fi n=m=250 si toate elementele matricii 250, caz in care depaseste short. Gresesc cumva?

[•DraStiK]

Teoretic nu ar trebui sa functioneze asa pentru ca ar putea fi n=m=250 si toate elementele matricii 250, caz in care depaseste short. Gresesc cumva?

Tipul de date short int retine numere pana la 2^16, deci dacă ai numere pana la 250, ar trebui sa intre.

[•PlayLikeNeverB4]

Da, dar, din cate am inteles eu, el spunea sa declaram si matricea pentru suma minima tot short. 250*250 > 32767. Cred ca merge cu unsigned short.

[•mihai.plesa]

Imi puteti da niste indicatii de rezolvare? Eu cred ca se rezolva cu ajutorul programarii dinamice dar nu stiu cum....va rog niste indicatii.
Multumesc!