0166 - SecvMax

Sursa: 0166 - SecvMax

---

Cerinţa

Se dau n numere naturale, reprezentând elementele unui vector.

Determinați cea mai lungă secvență de elemente pare din vector. Dacă există mai multe secvențe cu lungime maximă se va determina cea cu suma elementelor maximă. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga.

Date de intrare

Fişierul de intrare secvmax.in conţine numărul n și n valori naturale, reprezentând elementele vectorului. Valorile din fișier pot fi dispuse pe mai multe linii.

Date de ieșire

Fişierul de ieşire secvmax.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 secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 0 < n ≤ 10.000
• elementele vectorului vor fi mai mici decât 1000 și sunt numerotate de la 1

Exemplu 1

Intrare

secvk.in

9

2 6 4 5 8 8 6 3 4

Ieșire

secvk.out

Datele sunt introduse corect.

5 7

Exemplu 1

Intrare

secvk.in

9

2 6 4 5 8 8 6 3 4

Ieșire

secvk.out

Datele nu corespund restricțiilor impuse.

2 3 4 5

Rezolvare

Rezolvare ver. 1

#0166 - SecvMax

def citire_date():
    n = int(input())
    v = list(map(int, input().split()))
    return n, v

def secvmax(n, v):
    st = dr = st_max = dr_max = suma_max = suma = 0
    for i in range(n):
        if v[i] % 2 == 0:
            suma += v[i]
            dr = i
            if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
                suma_max = suma
                st_max = st
                dr_max = dr
        else:
            suma = 0
            st = i + 1
    return st_max + 1, dr_max + 1

def validare(n, v):
    if len(v) != n:
        print("Datele nu corespund restricțiilor impuse.")
        return False
    for x in v:
        if x < 0 or x > 1000:
            print("Datele nu corespund restricțiilor impuse.")
            return False
    print("Datele sunt introduse corect.")
    return True

if __name__ == '__main__':
    n, v = citire_date()
    if validare(n, v):
        st, dr = secvmax(n, v)
        print(st, dr, sep="\n")

Explicatie Rezolvare

Funcția citire_date primește de la tastatură numărul de elemente ale vectorului și apoi vectorul propriu-zis, pe care îl returnează sub formă de tuplu.

Funcția secvmax primește ca argumente numărul de elemente ale vectorului și vectorul și calculează cea mai lungă secvență de elemente pare din vector, folosind variabilele st și dr pentru a păstra indicii de început și de sfârșit ai secvenței curente și variabilele st_max și dr_max pentru a păstra indicii de început și de sfârșit ai secvenței cu suma maximă și variabila suma pentru a păstra suma elementelor din secvența curentă și variabila suma_max pentru a păstra suma elementelor din secvența cu suma maximă.

Funcția validare primește ca argumente numărul de elemente ale vectorului și vectorul și verifică dacă datele de intrare respectă condițiile impuse de cerință.

În funcția main, se citește datele de intrare, se validează și se afișează rezultatul dacă datele de intrare sunt valide, sau un mesaj de eroare altfel.