3659 - SumMaxSecv

Pentru că e criză, cu ocazia campaniei electorale, în loc de găleți pline cu făină, zahăr și bilete la teatru primiți un șir a1, a2, …, an care reprezintă o permutare a mulțimii {1,2,...,n}. Pentru fiecare secvență nevidă a permutării costul ei este valoarea maximă din acea secvență. De exemplu, costul secvenței 4,2,6,1,3,5 este 6, iar costul secvenței 4,2 este 4. Cerinta: Să se calculeze suma totală a costurilor tuturor secvențelor. Date de intrare: Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații. Restrictii: 2 ≤ n ≤ 100.000 șirul de numere este o permutare a mulțimii {1,2,...,n} Exemplu: Intrare: 4 2 3 4 1 Iesire: 33 Rezolvare:<syntaxhighlight lang="python"> def suma_costuri_permutare(perm):

   n = len(perm)
   cost_total = 0
   for i in range(n):
       max_val = perm[i]
       for j in range(i, n):
           max_val = max(max_val, perm[j])
           cost_total += max_val
   return cost_total

1. Citirea valorii lui n

n = int(input("Introduceți numărul n: "))

1. Citirea listei de n numere naturale separate prin spații

print(f"Introduceți {n} numere naturale separate prin spații:") input_numbers = input().split() # Citim input-ul și îl despărțim într-o listă de string-uri

1. Convertim fiecare element din listă într-un număr întreg

permutare = [int(num) for num in input_numbers]

1. Verificam daca permutarea are exact n elemente

if len(permutare) != n:

   print("Numărul introdus de elemente nu corespunde cu n.")

else:

   rezultat = suma_costuri_permutare(permutare)

   print(f"Suma costurilor tuturor secvențelor este: {rezultat}")

</syntaxhighlight>