0283 - Secventa

Sursa: - 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 pe prima linie două numere p şi u, separate printr-un spaţiu, reprezentând indicele primului, respectiv al ultimului element din secvenţa determinată.

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

Intrare

10

2 4 3 6 7 5 2 5 8 10

Ieșire

6 9

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0283 - Secventa

def citire():

   with open("secventa.in", "r") as f:
       n = int(f.readline())
       a = []
       for i in range(n):
           a.extend(map(int, f.readline().split()))
   return n, a

def rezolvare(n, a):

   p = u = -1  # poziția de început și de sfârșit a secvenței maxime
   max_lungime = max_suma = 0  # lungimea și suma maximă găsite până acum

   # parcurgem șirul și căutăm secvența 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(str(p+1) + " " + str(u+1) + "\n")

if __name__ == "__main__":

   n, a = citire()
   p, u = rezolvare(n, a)
   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.