Zmicala Narcis: Pagină nouă: 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...

2024-01-03T15:15:54Z

Pagină nouă: 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...

New page

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>

3652 - secvcost - Revision history