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	#56988324	Utilizator	Stoleriu Radu (RaduStoleriu)
Fișier	summax1.cpp	Dimensiune	2.68 KB
Data încărcării	12 Martie 2025, 13:45	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

summax1.cpp: In function 'int main()':
summax1.cpp:49:40: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type&, int)'
                 a[i][j]=min(a[i][j],INF);

                                        ^
summax1.cpp:49:40: note: candidates are:
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/ios:40,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from summax1.cpp:1:
/usr/include/c++/4.8/bits/stl_algobase.h:193:5: note: template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:193:5: note:   template argument deduction/substitution failed:
summax1.cpp:49:40: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
                 a[i][j]=min(a[i][j],INF);

                                        ^
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/ios:40,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from summax1.cpp:1:
/usr/include/c++/4.8/bits/stl_algobase.h:239:5: note: template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:239:5: note:   template argument deduction/substitution failed:
summax1.cpp:49:40: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
                 a[i][j]=min(a[i][j],INF);

                                        ^
summax1.cpp:71:40: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type&, int)'
                 a[i][j]=min(a[i][j],INF);

                                        ^
summax1.cpp:71:40: note: candidates are:
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/ios:40,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from summax1.cpp:1:
/usr/include/c++/4.8/bits/stl_algobase.h:193:5: note: template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:193:5: note:   template argument deduction/substitution failed:
summax1.cpp:71:40: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
                 a[i][j]=min(a[i][j],INF);

                                        ^
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/ios:40,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from summax1.cpp:1:
/usr/include/c++/4.8/bits/stl_algobase.h:239:5: note: template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:239:5: note:   template argument deduction/substitution failed:
summax1.cpp:71:40: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
                 a[i][j]=min(a[i][j],INF);

                                        ^

Cum funcționează evaluarea?