Soluții trimise

Pe un deal frumos
De la Chinteni în jos
Îndelung privește
Și se tot gândește
Un student din anul doi
“Mai bine aș fi cioban, la oi!”

Și atunci merge la stăpânul stânii să se angajeze pe o funcție de conducere, adică pe job-ul de cioban. Vasile, stăpânul stânii, e și el absolvent de informatică, așa că la interviul de angajare îi dă următoarea problemă:

Dealul pe care se află stâna este împărțit in n*m sectoare și a fost cosit. În fiecare sector se află o cantitate cunoscută de fân. Trebuie să parcurgi dealul de la Nord la Sud, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi dealul. La trecerea printr-un sector, trebuie colectat tot fânul din acel sector. Care cantitatea totală maximă de fân pe care o poți colecta, parcurgând astfel dealul, știind că pleci din orice sector al liniei 1 (Nord) și te oprești în orice sector al liniei n (Sud), cu respectarea condițiilor de mai sus?

Studentul râde, deoarece a rezolvat probleme similare în clasa a XI-a. Atunci Vasile complică problema cu o condiție suplimentară: se poate trece dintr-un sector în altul conform direcțiilor de mai sus doar dacă cantitațile de fân din cele două sectoare au parități diferite.