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	#48042036	Utilizator	Melvin Abibula (MelvinTheWizard)
Fișier	summax1.cpp	Dimensiune	1.93 KB
Data încărcării	14 Ianuarie 2024, 02:18	Scor / rezultat	0 puncte

Evaluare

Mesaj compilare

summax1.cpp: In function 'void cerinta2(int)':
summax1.cpp:22:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(p <= dp[i][x])

                            ^
summax1.cpp: In function 'int main()':
summax1.cpp:66:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(v[i + 1][j] == max1)

                               ^
summax1.cpp:71:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(v[i + 1][j + 1] == max1)

                                   ^
summax1.cpp:73:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(v[i + 1][j] != max1)

                                   ^
summax1.cpp:37:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("summax.in",  "r", stdin);

                                      ^
summax1.cpp:38:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("summax.out", "w", stdout);

                                       ^

Rezultat evaluare

Cum funcționează evaluarea?