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	#53709161	Utilizator	sofronea Vlad (vladsoarta)
Fișier	summax1.cpp	Dimensiune	1.68 KB
Data încărcării	09 Noiembrie 2024, 11:08	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

summax1.cpp:3:13: error: variable 'std::ifstream cin' has initializer but incomplete type
 ifstream cin("summax1.in");

             ^
summax1.cpp:4:14: error: variable 'std::ofstream cout' has initializer but incomplete type
 ofstream cout("summax1.out");

              ^
summax1.cpp: In function 'int main()':
summax1.cpp:15:5: error: reference to 'cin' is ambiguous
     cin>>c;

     ^
summax1.cpp:3:10: note: candidates are: <typeprefixerror>cin
 ifstream cin("summax1.in");

          ^
In file included from summax1.cpp:1:0:
/usr/include/c++/4.8/iostream:60:18: note:                 std::istream std::cin
   extern istream cin;  /// Linked to standard input
                  ^
summax1.cpp:16:5: error: reference to 'cin' is ambiguous
     cin>>n>>st>>dr;

     ^
summax1.cpp:3:10: note: candidates are: <typeprefixerror>cin
 ifstream cin("summax1.in");

          ^
In file included from summax1.cpp:1:0:
/usr/include/c++/4.8/iostream:60:18: note:                 std::istream std::cin
   extern istream cin;  /// Linked to standard input
                  ^
summax1.cpp:20:13: error: reference to 'cin' is ambiguous
             cin>>tricomb[i][j];

             ^
summax1.cpp:3:10: note: candidates are: <typeprefixerror>cin
 ifstream cin("summax1.in");

          ^
In file included from summax1.cpp:1:0:
/usr/include/c++/4.8/iostream:60:18: note:                 std::istream std::cin
   extern istream cin;  /// Linked to standard input
                  ^
summax1.cpp:54:9: error: reference to 'cout' is ambiguous
         cout<<tricomb[n][n+1];

         ^
summax1.cpp:4:10: note: candidates are: <typeprefixerror>cout
 ofstream cout("summax1.out");

          ^
In file included from summax1.cpp:1:0:
/usr/include/c++/4.8/iostream:61:18: note:                 std::ostream std::cout
   extern ostream cout;  /// Linked to standard output
                  ^

Cum funcționează evaluarea?