View source for 3652 - secvcost

Se dă un șir '''V''' de '''N''' numere naturale distincte. O secvență '''[X, Y]''' este formată din toate pozițiile consecutive dintre '''X''' și '''Y''' din șir. Se definește costul unei poziții '''P''' ca fiind valoarea din șir de pe poziția '''P''' înmulțită cu lungimea maximă a unei secvențe care conține poziția '''P''' și a cărei valoare maximă se află tot pe poziția '''P'''.
== Cerința ==
Se dau '''M''' întrebări de forma: '''X Y''' – să se calculeze suma tuturor costurilor pozițiilor din secvența '''[X, Y]'''.
Atenție! Când se calculează costul unei poziții P din '''[X, Y]''', secvența de lungime maximă pe care valoarea '''V[P]''' este maximă se calculează în funcție de tot șirul, NU în funcție de secvența '''[X, Y]''' (pentru clarificare urmăriți exemplul).
== Date de intrare ==
Fișierul de intrare '''secvcostin.txt''' conține pe prima linie cele două numere '''N''' și '''M''', separate prin spațiu. Pe a doua linie se află '''N''' numere naturale distincte reprezentând elementele șirului '''V'''. Pe următoarele '''M''' linii se află perechi de valori '''X''', '''Y''' reprezentând întrebările la care trebuie să se răspundă.
== Date de ieșire ==
Fișierul de ieșire '''secvcostout.txt''' va conține '''M''' linii cu câte un număr pe fiecare linie reprezentând răspunsul la cele '''M''' întrebări, în ordine.
== Restricții și precizări ==
* Toate valorile din șir sunt mai mici sau egale decât 5.000.000
* Pentru 25% din teste '''N, M ≤ 500'''
* Pentru alte 25% din teste '''N, M ≤ 10.000'''
* Pentru restul de 50% din teste '''N, M ≤ 200.000'''
== Exemplul 1 ==
; secvcostin.txt
: 5 2
: 2 3 1 5 4
: 3 3
: 2 2
; secvcostout.txt
: Datele introduse corespund restricțiilor impuse. 
: 1
: 9
== Explicație ==
Pentru prima întrebare avem '''V[3] = 1''' care este maxim pe secvența '''[3, 3]'''. Costul este '''1 * 1 = 1'''. Pentru a doua întrebare avem '''V[2] = 3''' care este maxim pe secvența '''[1, 3]'''. Costul este '''3 * 3 = 9'''.
== Exemplul 2 == 
; secvcostin.txt
: 5 3
: 2 3 1 5 4
: 1 3
: 5 5
: 4 4
; secvcostout.txt
: Datele introduse corespund restricțiilor impuse.
: 12
: 4
: 25
== Explicație ==
'''2*1 + 3*3 + 1*1 = 12'''
'''4*1 = 4'''
'''5*5 = 25'''
== Exemplul 3 ==
; secvcostin.txt
: 10 10
: 10 30 29 39 34 32 3 6 7 9
: 6 7
: 1 7
: 6 10
: 1 5
: 7 9
: 4 7
: 3 7
: 5 6
: 3 7
: 6 10
; secvcostout.txt
: Datele introduse corespund restricțiilor impuse.
: 163
: 886
: 232
: 723
: 36
: 757
: 786
: 364
: 786
: 232
== Exemplul 4 == 
; secvcostin.txt
: 5 2
: 2 3 1 5 6000000
: 3 3
: 2 2
; secvcostout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 3652 - secvcost
def validare(date1):           # functia de validare a datelor de intrare
    numar_elemente, numar_intrebari = map(int, date1[0].split())
    if not (1 <= numar_elemente <= 200000) or not (1 <= numar_intrebari <= 200000):
        raise ValueError

    sir = list(map(int, date1[1].split()))
    if len(sir) != numar_elemente or any(element > 5000000 for element in sir):
        raise ValueError

    intrebari = [list(map(int, date1[i].split())) for i in range(2, 2 + numar_intrebari)]
    if any(not (1 <= X <= Y <= numar_elemente) for X, Y in intrebari):
        raise ValueError

    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def cost_secventa(date1):                     # functia de rezolvare
    numar_elemente, numar_intrebari = map(int, date1[0].split())
    sir = list(map(int, date1[1].split()))
    intrebari = [list(map(int, date1[i].split())) for i in range(2, 2 + numar_intrebari)]
    for X, Y in intrebari:
        cost = sum([sir[i] * max(len(sir[:i+1]), len(sir[i:])) for i in range(X-1, Y)])
        fisier_iesire.write(f"{cost}\n")


if __name__ == '__main__':
    fisier_intrare = open("secvcostin.txt", "r")         # declararea fisierelor
    fisier_iesire = open("secvcostout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    # din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
    try:
        date = fisier_intrare.readlines()      # citirea numerelor se face ca sir de caractere

        validare(date)                 # apelul functiei de validare
        cost_secventa(date)               # apelul functiei de rezolvare

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>