0524 - SecvEgale1

De la Universitas MediaWiki

Sursa: 0524 - SecvEgale1


Cerinţa

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente din vector care începe și se termină cu aceeași valoare. Dacă în vector există mai multe secvențe corecte de lungime maximă se va determina cea mai din stânga.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, 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 ≤ 1000
  • cele n numere citite vor fi mai mici decât 1.000.000.000
  • indexarea elementelor vectorului începe de la 1.

Exemplu

Intrare
12
6 6 8 3 6 6 3 8 4 3 3 4
Ieșire
Datele nu corespund restricțiilor impuse.
4 11

Rezolvare

Rezolvare ver. 1

# 0524 - SecvEgale1

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


def determina_secventa_maxima(n, v):
    st, dr = -1, -1
    for i in range(n):
        if v[i] == v[0]:
            j = i
            while j < n and v[j] == v[i]:
                j += 1
            if j - i > dr - st:
                st, dr = i, j - 1
    return st, dr


def valideaza_datele_intrare(n, v):
    return len(v) == n and n > 0 and n <= 1000 and max(v) < 1000


if __name__ == '__main__':
    n, v = citeste_date_intrare()
    if valideaza_datele_intrare(n, v):
        st, dr = determina_secventa_maxima(n, v)
        if st == -1 and dr == -1:
            print("NU")
        else:
            print(st + 1, dr + 1)
    else:
        print("Datele nu corespund restricțiilor impuse.")

Explicatie Rezolvare

Funcția citeste_date_intrare citește de la tastatură numerele n și elementele vectorului v și le returnează ca o listă de întregi.

Funcția determina_secventa_maxima primește vectorul v și returnează indicii st și dr ai capetelor secvenței determinate.

Funcția valideaza_datele_intrare primește vectorul v și returnează True dacă datele de intrare sunt valide și False altfel. În acest caz, verificăm doar dacă vectorul nu este gol.

În funcția main, mai întâi citim datele de intrare și verificăm dacă sunt valide. Apoi, determinăm secvența maximă și afișăm indicii capetelor secvenței sau mesajul "NU", dacă nu există nicio secvență.