Rezumat problemă

Chinteni

#4937

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.

Fișiere Muresan Ciprian (mcip1977) medie

Clasa 11 Programare dinamică Probleme diverse de programare dinamică

Rezolvă

Detalii

Problema	Chinteni	Operații I/O	chinteni.in/chinteni.out
Limita timp	0.1 secunde	Limita memorie	Total: 64 MB / Stivă 8 MB
Id soluție	#64402055	Utilizator	Bajenaru Catalin (BajenaruCatalin)
Fișier	chinteni.cpp	Dimensiune	1.37 KB
Data încărcării	05 Mai 2026, 11:48	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

chinteni.cpp: In function ‘int main()’:
chinteni.cpp:30:15: warning: operation on ‘b’ may be undefined [-Wsequence-point]
   30 |             b = (a % 2 == b%2)?b=-1:b=b;
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
chinteni.cpp:31:15: warning: operation on ‘c’ may be undefined [-Wsequence-point]
   31 |             c = (a % 2 == c%2)?c=-1:c=c;
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
chinteni.cpp:32:15: warning: operation on ‘d’ may be undefined [-Wsequence-point]
   32 |             d = (a % 2 == d%2)?d=-1:d=d;
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
chinteni.cpp:38:19: warning: operation on ‘e’ may be undefined [-Wsequence-point]
   38 |                 e = (b == -1)?e=-1:e=dp[i-1][j];
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chinteni.cpp:39:19: warning: operation on ‘f’ may be undefined [-Wsequence-point]
   39 |                 f =(c == -1)?f=-1:f=dp[i-1][j-1];
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chinteni.cpp:40:19: warning: operation on ‘g’ may be undefined [-Wsequence-point]
   40 |                 g = (d == -1)?g=-1:g=dp[i-1][j+1];
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Rezultat evaluare

Cum funcționează evaluarea?