Rezumat problemă

#1623 SumMax1

Avem o matrice triunghiulară cu n linii, cu elemente numere întregi. În această matrice putem construi un traseu după următoarea regulă:

• primul element al traseului este elementul a1,1
• dacă elementul ai,j aparţine traseului, atunci următorul element al traseului poate fi doar ai+1,j sau a_i+1,j+1, pentru orice 1≤j≤i<n.
• traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la 1 la n. Valoarea traseului este egală cu suma elementelor ce îl formează.
  Traseul evidenţiat în exemplul din dreapta are valoarea 5+4+6+5+4=24, şi se codifică cu 1,2,3,3,4.

Fie mulţimea tuturor traseelor de valoare maximă generate în ordine lexicografică și numerotate. Pentru exemplul de mai sus avem șase trasee de lungime maximă:

• traseul 1. 1 1 1 1 2 (5+2+7+6+4=24)
• traseul 2. 1 1 1 2 2 (5+2+7+6+4=24)
• traseul 3. 1 2 2 2 2 (5+4+5+6+4=24)
• traseul 4. 1 2 3 3 4 (5+4+6+5+4=24)
• traseul 5. 1 2 3 4 4 (5+4+6+5+4=24)
• traseul 6. 1 2 3 4 5 (5+4+6+5+4=24)

Cunoscând dimensiunea și elementele unei matrice triunghiulare, respectiv două numere naturale st şi dr (st≤dr), se cere să se determine:

1. Numărul total al traseelor de valoare maximă. În cazul în care această valoare depășește 2000000000, se va tipări valoarea 2000000001;
2. Traseele cu numerele de ordine st, st+1, … , dr.

OJI 2016, Clasele XI-XII

• Fișiere
• Candale Silviu (silviu)
• Zoltan Szabo
• concurs

• Clasa 11 Programare dinamică Probleme diverse de programare dinamică

Rezolvă

Detalii

Problema	SumMax1	Operații I/O	summax1.in/summax1.out
Limita timp	2 secunde	Limita memorie	Total: 16 MB / Stivă 16 MB
Id soluție	#49357671	Utilizator	Chiper Ștefan😎 (stefanchp)
Fișier	summax1.cpp	Dimensiune	2.91 KB
Data încărcării	27 Februarie 2024, 15:26	Scor / rezultat	85 puncte

Evaluare

Mesaj compilare

summax1.cpp: In function 'void Drum(int, int, int)':
summax1.cpp:47:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if( DP(i, j) == x + y && x != 0 && y != 0 )

                             ^
summax1.cpp:54:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if( DP(i, j) == x && DP(i, j) != y )

                              ^
summax1.cpp:54:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if( DP(i, j) == x && DP(i, j) != y )

                                               ^
summax1.cpp:58:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if( DP(i, j) != x && DP(i, j) == y )

                              ^
summax1.cpp:58:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if( DP(i, j) != x && DP(i, j) == y )

                                               ^
summax1.cpp:62:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if( DP(i, j) == x && DP(i, j) == y )

                              ^
summax1.cpp:62:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if( DP(i, j) == x && DP(i, j) == y )

                                               ^
summax1.cpp: In function 'void Rezolvare()':
summax1.cpp:104:13: warning: unused variable 'mx' [-Wunused-variable]
         int mx = 0;

             ^

Rezultat evaluare

Cum funcționează evaluarea?