Soluții trimise

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 ai+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.
ID   Utilizator Problema Data încărcării Stare
leo messi (ankaramessi10) SumMax1 25 Martie 2024, 17:00 Evaluare finalizată E.C
Tomita Matey (mateytomita) SumMax1 20 Martie 2024, 14:06 Evaluare finalizată 100
Tomita Matey (mateytomita) SumMax1 20 Martie 2024, 14:03 Evaluare finalizată 20
Tomita Matey (mateytomita) SumMax1 20 Martie 2024, 12:19 Evaluare finalizată 20
Arustei Stefan (stefan_arustei) SumMax1 15 Martie 2024, 15:25 Evaluare finalizată 100
Arustei Stefan (stefan_arustei) SumMax1 15 Martie 2024, 14:59 Evaluare finalizată 0
Arustei Stefan (stefan_arustei) SumMax1 15 Martie 2024, 14:58 Evaluare finalizată 0
Arustei Stefan (stefan_arustei) SumMax1 15 Martie 2024, 14:57 Evaluare finalizată 0
Arustei Stefan (stefan_arustei) SumMax1 15 Martie 2024, 14:52 Evaluare finalizată 0
Arustei Stefan (stefan_arustei) SumMax1 15 Martie 2024, 14:50 Evaluare finalizată 0
Lautaru Bianca (biancalautaru) SumMax1 15 Martie 2024, 13:45 Evaluare finalizată 100
E N (griffin) SumMax1 14 Martie 2024, 17:47 Evaluare finalizată 20
E N (griffin) SumMax1 14 Martie 2024, 17:47 Evaluare finalizată 100
E N (griffin) SumMax1 14 Martie 2024, 17:46 Evaluare finalizată 10
E N (griffin) SumMax1 14 Martie 2024, 17:46 Evaluare finalizată 0
E N (griffin) SumMax1 14 Martie 2024, 17:39 Evaluare finalizată 10
E N (griffin) SumMax1 14 Martie 2024, 17:37 Evaluare finalizată 10
E N (griffin) SumMax1 14 Martie 2024, 17:21 Evaluare finalizată 5
E N (griffin) SumMax1 14 Martie 2024, 17:18 Evaluare finalizată 5
E N (griffin) SumMax1 14 Martie 2024, 17:01 Evaluare finalizată 5
E N (griffin) SumMax1 14 Martie 2024, 16:56 Evaluare finalizată 0
E N (griffin) SumMax1 14 Martie 2024, 16:55 Evaluare finalizată 5
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 16:20 Evaluare finalizată 20
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 15:32 Evaluare finalizată 10
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 14:57 Evaluare finalizată 15
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 14:56 Evaluare finalizată 15
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 14:53 Evaluare finalizată 10
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 14:50 Evaluare finalizată 10
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 14:31 Evaluare finalizată 10
Pop George </> (Pop_George) SumMax1 14 Martie 2024, 14:29 Evaluare finalizată 0
Damian Alex (alexdmn) SumMax1 13 Martie 2024, 18:02 Evaluare finalizată 0
Damian Alex (alexdmn) SumMax1 13 Martie 2024, 17:59 Evaluare finalizată 0
Damian Alex (alexdmn) SumMax1 13 Martie 2024, 17:59 Evaluare finalizată 0
Stefanescu Ecaterina (ecaterina_stefanescu) SumMax1 13 Martie 2024, 12:13 Evaluare finalizată 20
Stefanescu Ecaterina (ecaterina_stefanescu) SumMax1 13 Martie 2024, 12:06 Evaluare finalizată 0
Stefanescu Ecaterina (ecaterina_stefanescu) SumMax1 13 Martie 2024, 12:01 Evaluare finalizată 0
Stefanescu Ecaterina (ecaterina_stefanescu) SumMax1 13 Martie 2024, 12:00 Evaluare finalizată 0
Donciu Arin (BasescuIon) SumMax1 13 Martie 2024, 09:57 Evaluare finalizată 100
Donciu Arin (BasescuIon) SumMax1 13 Martie 2024, 09:56 Evaluare finalizată 100
Donciu Arin (BasescuIon) SumMax1 13 Martie 2024, 09:36 Evaluare finalizată 30
Donciu Arin (BasescuIon) SumMax1 13 Martie 2024, 09:34 Evaluare finalizată E.C
Donciu Arin (BasescuIon) SumMax1 13 Martie 2024, 09:34 Evaluare finalizată 30
Donciu Arin (BasescuIon) SumMax1 13 Martie 2024, 09:32 Evaluare finalizată 30
Turcu Alex (panterasbook29) SumMax1 13 Martie 2024, 09:17 Evaluare finalizată E.C
Cristiana Balcanu (pancakes) SumMax1 13 Martie 2024, 09:10 Evaluare finalizată 100
Cristiana Balcanu (pancakes) SumMax1 13 Martie 2024, 08:50 Evaluare finalizată 20
Donciu Arin (BasescuIon) SumMax1 12 Martie 2024, 22:17 Evaluare finalizată 0
Donciu Arin (BasescuIon) SumMax1 12 Martie 2024, 22:15 Evaluare finalizată 0
Pavel Stefan (LevapNafets) SumMax1 12 Martie 2024, 20:32 Evaluare finalizată E.C
Donciu Arin (BasescuIon) SumMax1 12 Martie 2024, 20:22 Evaluare finalizată 20