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

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>