Rezumat problemă

SumMax1

#1623

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	#55416514	Utilizator	Martinut Federica (Federicamartinut)
Fișier	summax1.cpp	Dimensiune	1.20 KB
Data încărcării	14 Ianuarie 2025, 12:33	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

summax1.cpp: In function 'int main()':
summax1.cpp:20:25: error: invalid types 'int[int]' for array subscript
            cin >> d[i][j];

                         ^
summax1.cpp:21:34: error: invalid types 'int[int]' for array subscript
  for (j = 1; j <=n; ++j) cnt[i][j] = 1;

                                  ^
summax1.cpp:26:10: error: invalid types 'int[int]' for array subscript
    d[i][j] = max(d[i + 1][j], d[i + 1][j + 1]) + d[i][j];

          ^
summax1.cpp:26:28: error: invalid types 'int[int]' for array subscript
    d[i][j] = max(d[i + 1][j], d[i + 1][j + 1]) + d[i][j];

                            ^
summax1.cpp:26:45: error: invalid types 'int[int]' for array subscript
    d[i][j] = max(d[i + 1][j], d[i + 1][j + 1]) + d[i][j];

                                             ^
summax1.cpp:26:56: error: invalid types 'int[int]' for array subscript
    d[i][j] = max(d[i + 1][j], d[i + 1][j + 1]) + d[i][j];

                                                        ^
summax1.cpp:27:18: error: invalid types 'int[int]' for array subscript
    if (d[i + 1][j] == d[i + 1][j + 1])

                  ^
summax1.cpp:27:37: error: invalid types 'int[int]' for array subscript
    if (d[i + 1][j] == d[i + 1][j + 1])

                                     ^
summax1.cpp:29:13: error: invalid types 'int[int]' for array subscript
     cnt[i][j] = cnt[i + 1][j] + cnt[i + 1][j + 1];

             ^
summax1.cpp:29:29: error: invalid types 'int[int]' for array subscript
     cnt[i][j] = cnt[i + 1][j] + cnt[i + 1][j + 1];

                             ^
summax1.cpp:29:49: error: invalid types 'int[int]' for array subscript
     cnt[i][j] = cnt[i + 1][j] + cnt[i + 1][j + 1];

                                                 ^
summax1.cpp:30:17: error: invalid types 'int[int]' for array subscript
     if (cnt[i][j] > 2000000000)

                 ^
summax1.cpp:31:14: error: invalid types 'int[int]' for array subscript
      cnt[i][j] = 2000000001;

              ^
summax1.cpp:33:23: error: invalid types 'int[int]' for array subscript
    else if (d[i + 1][j] > d[i + 1][j + 1])

                       ^
summax1.cpp:33:41: error: invalid types 'int[int]' for array subscript
    else if (d[i + 1][j] > d[i + 1][j + 1])

                                         ^
summax1.cpp:34:13: error: invalid types 'int[int]' for array subscript
     cnt[i][j] = cnt[i + 1][j];

             ^
summax1.cpp:34:29: error: invalid types 'int[int]' for array subscript
     cnt[i][j] = cnt[i + 1][j];

                             ^
summax1.cpp:35:17: error: invalid types 'int[int]' for array subscript
    else cnt[i][j] = cnt[i + 1][j + 1];

                 ^
summax1.cpp:35:37: error: invalid types 'int[int]' for array subscript
    else cnt[i][j] = cnt[i + 1][j + 1];

                                     ^
summax1.cpp:38:30: error: invalid types 'int[int]' for array subscript
  if (c == 1) cout << cnt[1][1];

                              ^
summax1.cpp:48:19: error: invalid types 'int[int]' for array subscript
     if (d[i + 1][j] == d[i + 1][j + 1])

                   ^
summax1.cpp:48:38: error: invalid types 'int[int]' for array subscript
     if (d[i + 1][j] == d[i + 1][j + 1])

                                      ^
summax1.cpp:50:26: error: invalid types 'int[int]' for array subscript
      if (x > cnt[i + 1][j])

                          ^
summax1.cpp:52:27: error: invalid types 'int[int]' for array subscript
       x = x - cnt[i + 1][j];

                           ^
summax1.cpp:56:24: error: invalid types 'int[int]' for array subscript
     else if (d[i + 1][j] < d[i + 1][j + 1]) ++j;

                        ^
summax1.cpp:56:42: error: invalid types 'int[int]' for array subscript
     else if (d[i + 1][j] < d[i + 1][j + 1]) ++j;

                                          ^

Cum funcționează evaluarea?