1436 - Distanta Maxima

Cerința

Fie S un şir cu numere naturale nenule. Considerând distanţa dintre elementele Si şi Sj ca fiind egală cu |i−j|, scrieţi un program care determină distanţa maximă dintre două valori egale din şir.

Date de intrare

Fișierul de intrare distantain.txt conține pe prima linie maxim 100.000 de numere naturale, reprezentând elementele şirului S.

Date de ieșire

Fișierul de ieşire distantaout.txt va conţine pe prima linie distanţa maximă dintre două valori egale din şir. Dacă şirul are toate elementele distincte, distanţa va fi egală cu 0.

Restricții și precizări

• Fiecare element al şirului este un număr natural din intervalul [1,1000]
• Elementele şirului sunt numerotate de la 1

Exemplul 1

Intrare

distantain.txt

30 33 16 33 37 16 72 65 16 46

Ieșire

Datele de intrare corespund restricțiilor impuse

distantaout.txt

6

Explicație

S={30, 33, 16, 33, 37, 16, 72, 65, ;16, 46}. Distanţa maximă este cea dintre elementele subliniate (9−3=6).

Exemplul 2

Intrare

distantain.txt

1001 33 16 33 37 16 72 65 16 46

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1436 - Distanta maxima

def validare_sir(sir):
    elemente = sir.split()

    if len(elemente) > 100000:
        return False

    for elem in elemente:
        if not (elem.isdigit() and 1 <= int(elem) <= 1000):
            return False

    return True


def distanta_maxima(sir):
    elemente = sir.split()
    pozitii = {}
    max_distanta = 0

    for i, elem in enumerate(elemente):
        if elem in pozitii:
            distanta = i - pozitii[elem]
            max_distanta = max(max_distanta, distanta)
        else:
            pozitii[elem] = i

    return max_distanta


def main():
    with open("distantain.txt", "r") as f:
        sir = f.readline().strip()

    rezultat = 0

    if validare_sir(sir):
        print("Datele de intrare corespund restricțiilor impuse")
        rezultat = distanta_maxima(sir)
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)

    with open("distantaout.txt", "w") as f:
        f.write(str(rezultat) + "\n")


if __name__ == "__main__":
    main()