1439 - Sir6

Se dă un şir de N numere naturale. Din acest şir, putem forma un şir comprimat de forma: a[1], b[1], a[2], b[2], …, a[x], b[x], din care înţelegem că numărul a[1] apare pe primele b[1] poziţii, a[2] apare pe următoarele b[2] poziţii…, iar a[x] apare pe ultimele b[x] poziţii. De exemplu, dacă şirul dat este 1 1 5 5 5 2, atunci şirul comprimat va fi 1 2 5 3 2 1.

Cerința

Să se determine: a) Lungimea celei mai lungi secvenţe formată din numere egale. b) Şirul comprimat pentru şirul dat.

Date de intrare

Fișierul de intrare sir6in.txt conține pe prima linie numerele P şi N. Pe următoarea linie se găseşte un şir format din N numere naturale.

Date de ieșire

Fișierul de ieșire sir6out.txt va conține pe prima linie: a) Dacă P este 1, lungimea celei mai lungi secvenţe, reprezentând răspunsul la cerinţa a). b) Dacă P este 2, şirul comprimat, reprezentând răspunsul la cerinţa b). caz contrar, se va afișa mesajul:" Datele de intrare nu corespund restrictiilor impuse"

Restricții și precizări

• N <= 100.000
• Numerele din şir nu depăşesc 1.000.000.
• P este 1 sau 2.

Exemplul 1

sir6in.txt

1 6

1 1 5 5 5 2

sir6out.txt

Datele introduse corespund restricțiilor impuse.

3

Explicație

Pentru acest test P = 1, deci se va rezolva doar cerinţa a). Secvenţa cea mai lungă formată din numere egale este: 5 5 5 şi are lungimea 3.

Exemplul 2

sir6in.txt

2 6

1 1 5 5 5 2

sir6out.txt

Datele introduse corespund restricțiilor impuse.

1 2 5 3 2 1

Explicație

Pentru acest test P = 2, deci se va rezolva doar cerinţa b). Numărul 1 apare de 2 ori, numărul 5 apare de 3 ori, iar numărul 2 apare o singură dată. Prin urmare, şirul comprimat este 1 2 5 3 2 1.

Exemplul 3

sir6in.txt

2

1 2 3 4 5 1000000001

2

1 3

2 4

sir6out.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 1439 - Sir6
from itertools import groupby


def validare(p, numarde_elemente, sirul):           # functia de validare a datelor de intrare
    if p not in [1, 2] or not (1 <= numarde_elemente <= 100000):
        raise ValueError

    if any(not (0 <= element <= 1000000) for element in sirul):
        raise ValueError

    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def proceseaza_sir(p, sirul):                     # functia de rezolvare
    if p == 1:
        lungime_maxima = max(len(list(grup)) for _, grup in groupby(sirul))
        fisier_iesire.write(f"{lungime_maxima}\n")
    elif p == 2:
        sir_comprimat = [f"{k} {len(list(grup))}" for k, grup in groupby(sirul)]
        fisier_iesire.write(" ".join(sir_comprimat) + "\n")


if __name__ == '__main__':
    fisier_intrare = open("sir6in.txt", "r")         # declararea fisierelor
    fisier_iesire = open("sir6out.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        P, numar_elemente = map(int, fisier_intrare.readline().split())
        sir = list(map(int, fisier_intrare.readline().split()))

        validare(P, numar_elemente, sir)                 # apelul functiei de validare
        proceseaza_sir(P, sir)               # apelul functiei de rezolvare

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")