2840 - Secventa Uniforma

Cerinţa

Numim secvență uniformă a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași valoare, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia.

Se dă un șir de cel puțin două și cel mult 1000000 de numere naturale din intervalul [0,10^9]. În șir există cel puțin doi termeni egali pe poziții consecutive. Se cere să se determine o secvență uniformă de lungime maximă în șirul dat și să se afișeze pe lungimea acestei secvențe și termenii acesteia. Dacă sunt mai multe astfel de secvențe, se afișează doar termenii ultimei dintre acestea.

Date de intrare

Fișierul de intrare secventauniforma.in conține pe prima linie un șir de cel puțin două și cel mult 1000000 de numere naturale din intervalul [0,10^9], separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",fișierul de ieșire secventauniforma.out va conține pe prima linie lungimea acestei secvențe și, pe o linie nouă, separați prin câte un spațiu, termenii acesteia.. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei necesare și al timpului de executare.
• Se recomandă evitarea memorării elementelor șirului într-un tablou sau în altă structură de date similară.

Exemple

Exemplul 1

secventauniforma.in

2 3 3 3 3 5 4 4 11 11 11 11 16 11 11 11 11 15 15

secventauniforma.out

Datele sunt introduse corect.

4

3 3 3 3

Exemplul 2

secventauniforma.in

5 5 5 5 5 5 5 5

secventauniforma.out

Datele sunt introduse corect.

8

5 5 5 5 5 5 5 5

Exemplul 2

secventauniforma.in

2 3 1000000001

iesire

Datele nu corespund restricțiilor impuse.

secventauniforma.out

Rezolvare

# 2840 - Secventa Uniforma
def valideaza_intrare(n: int, lst: list[int]) -> bool:
    """
    Verifică dacă datele de intrare sunt valide conform cerințelor.
    """
    if not (1 <= n <= 10**7) or len(lst) > n:
        return False
    for i in range(len(lst)):
        if not (1 <= lst[i] <= n):
            return False
        if i > 0 and lst[i] < lst[i-1]:
            return False
    if len(set(lst)) != len(lst):
        return False
    return True


def afiseaza_lipsa(nr_lipsa: list[int]) -> None:
    """
    Afișează numerele lipsă, ordonate crescător.
    """
    if nr_lipsa:
        print(*nr_lipsa)
    else:
        print("Nu exista")


def gaseste_numere_lipsa(n: int, lst: list[int]) -> list[int]:
    """
    Găsește numerele lipsă din intervalul [1, n] față de lista dată.
    """
    if not valideaza_intrare(n, lst):
        print("Datele nu corespund restricțiilor impuse.")
        return []
    nr_lipsa = []
    j = 1
    for nr in lst:
        while j < nr:
            nr_lipsa.append(j)
            j += 1
        j = nr + 1
    while j <= n:
        nr_lipsa.append(j)
        j += 1
    return nr_lipsa


# Citirea datelor de intrare din fișier
with open("numere25.in", "r") as f:
    # Citim n din prima linie a fișierului și îl convertim la int
    n = int(f.readline().strip())
    # Citim lista de numere din a doua linie a fișierului și o convertim la listă de int
    lst = list(map(int, f.readline().split()))

# Găsirea numerelor lipsă și afișarea lor
if valideaza_intrare(n, lst):
    # Dacă datele sunt valide, afișăm un mesaj corespunzător
    print("Datele sunt introduse corect.")
    # Calculăm numerele lipsă și le afișăm
    nr_lipsa = gaseste_numere_lipsa(n, lst)
    afiseaza_lipsa(nr_lipsa)
    # Scriem rezultatele în fișierul de ieșire
    with open("numere25.out", "w") as f:
        if nr_lipsa:
            f.write(" ".join(map(str, nr_lipsa)))
        else:
            f.write("Nu exista\n")
        # Adăugăm mesajul de validare în fișierul de ieșire
        if valideaza_intrare(n, lst):
            f.write("Datele sunt introduse corect.\n")
        else:
            f.write("Datele nu corespund restricțiilor impuse.\n")
    print("Fisierul de iesire a fost creat cu succes.")