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

Intrare

secventa.in

10 2 3 4

1 9 22 13 5 2 5 8 10

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 0283 - Secventa
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__":
    try:
        with open("secventa.in", "r") as f:
            n = int(f.readline())
            a = list(map(int, f.readline().split()))
        if n < 1 or n > 100000:
            raise ValueError("Numarul n nu se incadreaza in limitele problemei.")
        for i in range(n):
            if a[i] < 0 or a[i] > 999999999:
                raise ValueError("Elementele sirului trebuie sa fie numere naturale de cel mult 9 cifre.")
        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)
    except Exception as e:
        print("Datele nu corespund restricțiilor impuse.")
        print(e)

Explicatie Rezolvare

Funcția de rezolvare, rezolvare(n, a), care primește ca parametri numărul de elemente din șir n și șirul propriu-zis a. Scopul acestei funcții este de a determina cea mai lungă secvență cu proprietatea specificată în enunț și de a returna pozițiile primului și ultimului element din această secvență.

Această funcție începe prin a inițializa variabilele p și u cu valoarea -1, semnificând faptul că încă nu am găsit nicio secvență cu proprietatea specificată. De asemenea, funcția mai inițializează două variabile max_lungime și max_suma cu valoarea 0, care vor fi folosite pentru a determina secvența maximă în ceea ce privește lungimea și suma elementelor.

În continuare, se parcurge șirul a și se calculează lungimea și suma elementelor din secvența curentă, utilizând variabilele lungime_secventa și suma_elementelor. Dacă se întâlnește un element cu paritatea identică cu elementul anterior, secvența curentă se întrerupe și se inițializează lungimea și suma elementelor pentru o nouă secvență începând cu elementul curent. În caz contrar, se actualizează lungimea și suma elementelor din secvența curentă, și se compară aceste valori cu cele ale secvenței maximale găsite până în acel moment (max_lungime și max_suma). Dacă lungimea secvenței curente depășește lungimea secvenței maxime găsite până în acel moment, sau are lungime egală cu aceasta dar suma elementelor este mai mare, atunci secvența curentă devine noua secvență maximă și se actualizează variabilele max_lungime și max_suma. În plus, se actualizează și variabilele p și u cu pozițiile primului și ultimului element din secvența curentă, dacă este cazul.

Funcția de rezolvare returnează apoi variabilele p și u.

Funcția de validare, validare(p, u), primește ca parametri pozițiile primului și ultimului element din secvența maximă găsită de funcția rezolvare, și are rolul de a scrie aceste valori în fișierul de ieșire secventa.out. Dacă nu s-a găsit nicio secvență cu proprietatea specificată, funcția va scrie -1 în fișierul de ieșire.

În funcția principală if __name__ == "__main__", începem prin citirea datelor de intrare din fișierul `secventa.