0283 - Secventa

Cerinţa

Se dă un şir cu n elemente, numere naturale. Determinaţi cea mai lungă secvenţă de elemente din şir cu proprietatea că oricare două valori consecutive în secvenţă au parităţi diferite.

Dacă există mai multe secvente de lungime maximă cu această proprietate, se va determina aceea cu suma elementelor maximă. Dacă există mai multe secvenţe de lungime maximă cu aceeaşi sumă maximă a elementelor se va determina cea mai din dreapta.

Date de intrare

Fişierul de intrare secventa.in conţine pe prima linie numărul n; urmează cele n elemente ale şirului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Fişierul de ieşire secventa.out va conţine Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou două numere p şi u, separate printr-un spaţiu, reprezentând indicele primului, respectiv al ultimului element din secvenţa determinată, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ n ≤ 100.000;
elementele şirului vor avea cel mult 9 cifre şi sunt numerotate de la 1 la n;

Exemplu 1

Intrare: secventa.in; 10; 2 4 3 6 7 5 2 5 8 10
Ieșire: secventa.out; Datele sunt introduse correct.; 6 9

Exemplu 1

Intrare: secventa.in; 10 2 3 4; 1 9 22 13 5 2 5 8 10
Ieșire: secventa.out; Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

0283 - Secventa

def citire():

   try:
       with open("secventa.in", "r") as f:
           n = int(f.readline())
           a = list(map(int, f.readline().split()))
       return n, a
   except:
       print("Datele nu corespund restricțiilor impuse.")
       print("Datele nu sunt introduse corect.")

def rezolvare(n, a):

   p = u = -1
   max_lungime = max_suma = 0

   # Cautam secventa maximă
   lungime_secventa = suma_elementelor = 1
   for i in range(1, n):
       if a[i] % 2 == a[i-1] % 2:
           lungime_secventa = 1
           suma_elementelor = a[i]
       else:
           lungime_secventa += 1
           suma_elementelor += a[i]
           if lungime_secventa > max_lungime or (lungime_secventa == max_lungime and suma_elementelor > max_suma):
               max_lungime = lungime_secventa
               max_suma = suma_elementelor
               p = i - lungime_secventa + 1
               u = i

   return p, u

def validare(p, u):

   with open("secventa.out", "w") as f:
       if p == -1:
           f.write("-1\n")
       else:
           f.write(f"{p+1} {u+1}\n")

if __name__ == "__main__":

   n, a = citire()
   p, u = rezolvare(n, a)
   if p != -1 and u != -1:
       print("Datele sunt introduse corect.")
   else:
       print("Datele nu corespund restricțiilor impuse.")
   validare(p, u)

</syntaxhighlight>

Explicatie Rezolvare

Pentru rezolvarea acestei probleme, vom parcurge şirul dat şi vom folosi două variabile: lungimea_secvenţei pentru a memora lungimea secvenţei curente, şi suma_elementelor pentru a memora suma elementelor din secvenţa curentă. De asemenea, vom mai folosi două variabile: max_lungime pentru a memora lungimea maximă găsită până acum, şi max_suma pentru a memora suma maximă găsită până acum, precum şi două variabile: p pentru a memora poziţia de început a secvenţei maxime şi u pentru a memora poziţia de sfârşit a secvenţei maxime.

În timpul parcurgerii şirului, vom actualiza lungimea_secvenţei şi suma_elementelor pentru fiecare secvenţă găsită, şi vom compara cu valorile maxime găsite până acum, actualizându-le în caz că avem o secvenţă nouă mai bună.

După parcurgerea întregului şir, vom afişa valorile p şi u, adică poziţiile de început şi sfârşit ale secvenţei maxime.