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	#57079976	Utilizator	Cisteian Razvan (RazvanC_)
Fișier	summax1.cpp	Dimensiune	2.69 KB
Data încărcării	14 Martie 2025, 22:50	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

summax1.cpp:13:17: error: stray '#' in program
 bool verif(int i#include <bits/stdc++.h>

                 ^
summax1.cpp:13:18: error: expected ',' or '...' before 'include'
 bool verif(int i#include <bits/stdc++.h>

                  ^
summax1.cpp:14:20: error: expected ')' before ';' token
 using namespace std;

                    ^
summax1.cpp:16:13: error: redefinition of 'std::ifstream fin'
 ifstream fin("summax1.in");

             ^
summax1.cpp:4:10: error: 'std::ifstream fin' previously declared here
 ifstream fin("summax1.in");

          ^
summax1.cpp:17:14: error: redefinition of 'std::ofstream fout'
 ofstream fout("summax1.out");

              ^
summax1.cpp:5:10: error: 'std::ofstream fout' previously declared here
 ofstream fout("summax1.out");

          ^
summax1.cpp:19:5: error: redefinition of 'int cer'
 int cer, n, st, dr;

     ^
summax1.cpp:7:5: error: 'int cer' previously declared here
 int cer, n, st, dr;

     ^
summax1.cpp:19:10: error: redefinition of 'int n'
 int cer, n, st, dr;

          ^
summax1.cpp:7:10: error: 'int n' previously declared here
 int cer, n, st, dr;

          ^
summax1.cpp:19:13: error: redefinition of 'int st'
 int cer, n, st, dr;

             ^
summax1.cpp:7:13: error: 'int st' previously declared here
 int cer, n, st, dr;

             ^
summax1.cpp:19:17: error: redefinition of 'int dr'
 int cer, n, st, dr;

                 ^
summax1.cpp:7:17: error: 'int dr' previously declared here
 int cer, n, st, dr;

                 ^
summax1.cpp:20:17: error: redefinition of 'int a [1001][1001]'
 int a[1001][1001];

                 ^
summax1.cpp:8:5: error: 'int a [1001][1001]' previously declared here
 int a[1001][1001];

     ^
summax1.cpp:21:17: error: redefinition of 'int d [1001][1001]'
 int d[1001][1001];

                 ^
summax1.cpp:9:5: error: 'int d [1001][1001]' previously declared here
 int d[1001][1001];

     ^
summax1.cpp:22:17: error: redefinition of 'int t [1001][1001]'
 int t[1001][1001];

                 ^
summax1.cpp:10:5: error: 'int t [1001][1001]' previously declared here
 int t[1001][1001];

     ^
summax1.cpp:23:17: error: redefinition of 'int c [1001][1001]'
 int c[1001][1001];

                 ^
summax1.cpp:11:5: error: 'int c [1001][1001]' previously declared here
 int c[1001][1001];

     ^
summax1.cpp:87:1: error: mixing declarations and function-definitions is forbidden
 , int j){

 ^
summax1.cpp:87:3: error: expected unqualified-id before 'int'
 , int j){

   ^
summax1.cpp: In function 'int back(int, int)':
summax1.cpp:91:5: error: redefinition of 'int back(int, int)'
 int back(int i, int j){

     ^
summax1.cpp:29:5: error: 'int back(int, int)' previously defined here
 int back(int i, int j){

     ^
summax1.cpp: In function 'int calc(int, int)':
summax1.cpp:100:5: error: redefinition of 'int calc(int, int)'
 int calc(int i, int j){

     ^
summax1.cpp:40:5: error: 'int calc(int, int)' previously defined here
 int calc(int i, int j){

     ^
summax1.cpp: In function 'int main()':
summax1.cpp:116:5: error: redefinition of 'int main()'
 int main(){

     ^
summax1.cpp:60:5: error: 'int main()' previously defined here
 int main(){

     ^

Cum funcționează evaluarea?