Problema

[•danimihalca]

Buna. Ma puteti ajuta sa caut o problema? M-am gandit ca poate e pe infoarena, dar problema e ca o stiu doar din auzite, fara titlu. Am incercat diverse titluri, keywords in Search dar nimic. Deci problema e asa: un soricel se gaseste in coltul din stanga sus al unui labirint si trebuie sa ajunga in coltul opus (dreapta jos). Stiind ca soricelul poate merge doar de la stanga la dreapta, de sus in jos, si pe diagonala de pe pozitia (i,j) pe pozitia (i+1,j+1), sa se calculeze distanta maxima. Nu ma intereseaza solutia, ci limita de memorie/timp si un exemplu . Va multumesc.

[•pauldb]

Eu nu stiu sa existe problema aceasta pe infoarena.

[•gabitzish1]

Ai ceva obstacole in labirint si trebuiesc ocolite, sau ai costuri si tre sa fie suma cat mai mare?

[•danimihalca]

Costuri nu am, de obstacole nu mi-a zis nimic, dar poate ca sunt.

[•gabitzish1]

Daca n'ai obstacole, nici costuri, nu ti se pare ca drumul maxim e 2 * (N -1) iar drumul minim (N - 1) pe diagonala?
Dar cred ca nu stii enuntul complet ca e prea banal sa fie asa.

[•wefgef]

Nu cumva problema a fost data la OJI clasa a IX-a in urma cu multi ani?

[•danimihalca]

Posibil. Acum imi scot subiectele din anii trecuti de la OJI sa le verif.

LE: Am gasit-o. S-a dat la OJI 2002 la clasa a IX-a. M Mersi inca o data wefgef

[•wefgef]

Asta a fost prima problema de olimpiada pe care am facut-o vreodata .

[•ucc_5]

Chiar asa eu inca nu am gasit alta solutie decat sa fac cu grafuri (defapt lee modificat). Exista vreo solutie mai simpla ? ca ma indoiesc ca se dadea asa ceva la clasa a IXa, adica ar inseamna ca ce se da acu e floare la ureche.

[•APOCALYPTO]

Pe infoarena nu exista? Ca s-o pot face:(?