Vizualizare sursă pentru „3659 - SumMaxSecv”

== Enunț ==
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

== Cerință ==
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.

== Date de ieșire ==
Programul va afișa pe ecran numărul S, reprezentând suma costurilor tuturor secvențelor.

== Restricții și precizări ==
2 ≤ n ≤ 100.000

șirul de numere este o permutare a mulțimii {1,2,...,n}

== Exemplu ==
'''Intrare'''

4

2 3 4 1

'''Ieșire'''

33

== Explicație ==
Secvențele nevide ale permutării 2,3,4,1 sunt:

2 – cost 2

2 3 – cost 3

2 3 4 – cost 4

2 3 4 1 – cost 4

3 – cost 3

3 4 – cost 4

3 4 1 – cost 4

4 – cost 4

4 1 – cost 4

1 – cost 1

Costul total este 2+3+4+4+3+4+4+4+4+1=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

def valid_input(n, permutare):
    if n < 2 or n > 100000:
        print("Numărul n trebuie să fie între 2 și 100.000.")
        return False

    if len(permutare) != n or set(permutare) != set(range(1, n + 1)):
        print("Lista de numere nu reprezintă o permutare validă a mulțimii {1,2,...,n}.")
        return False

    return True

# Citirea valorii lui n
n = int(input("Introduceți numărul n: "))

# 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

# Convertim fiecare element din listă într-un număr întreg
permutare = [int(num) for num in input_numbers]

# Validare input
if valid_input(n, permutare):
    rezultat = suma_costuri_permutare(permutare)
    print(f"Suma costurilor tuturor secvențelor este: {rezultat}")
</syntaxhighlight>