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
# 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")
