Editing 0184 - Interval 1

== Cerinta ==

Se dă un şir de n numere întregi şi un număr k. Să se determine intervalul [a,b] de lungime minimă care conţine cel puţin k elemente din sir.

== Date de intrare ==

Fişierul de intrare interval1.txt conţine pe prima linie numerele n şi k, iar pe următoarele linii n numere întregi separate prin spaţii, reprezentând elementele şirului.

== Date de iesire ==

Fişierul de ieşire interval1.txt va conţine pe prima linie două numere a şi b, separate printr-un spaţiu, cu semnificaţia de mai sus.

== Restrictii si precizari ==

*1 ≤ k ≤ n ≤ 1000
*elementele şirului aparţin intervalului [-1000,1000] şi pot fi dispuse în fişierul de intrare pe mai multe linii
*dacă există mai multe intervale [a,b] de lungime minimă care conţin cel puţin k elemente din sir se va alege acela pentru care a este minim
*a ≤ b

== Exemplul 1 ==
;Intrare
:10 3
:11 9 3 2 8 11 9 10 15 13 
;Iesire
;Datele introduse corespund restrictiilor impuse
:8 9

== Exemplul 2 ==
;Intrare
:4 2
:20,5,100,75.2
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def gaseste_interval_minim(sir, n, k):
    a = b = 0  # Pointer-ele pentru intervalul minim [a, b]
    numere_gasite = 0  # Numărul de elemente găsite în interval

    # Inițializează un dicționar pentru a număra de câte ori apare fiecare element în interval
    frecventa_elemente = {}

    while b < n:
        # Extinde intervalul spre dreapta
        frecventa_elemente[sir[b]] = frecventa_elemente.get(sir[b], 0) + 1
        if frecventa_elemente[sir[b]] == 1:
            numere_gasite += 1

        # Dacă am găsit cel puțin k elemente, încercăm să restrângem intervalul spre stânga
        while numere_gasite >= k:
            # Verificăm dacă este intervalul minim și actualizăm rezultatul
            if b - a < b_min - a_min:
                a_min, b_min = a, b

            # Încercăm să restrângem intervalul spre stânga
            frecventa_elemente[sir[a]] -= 1
            if frecventa_elemente[sir[a]] == 0:
                numere_gasite -= 1
            a += 1

        # Extinde intervalul spre dreapta
        b += 1

    return a_min, b_min

def main():
    with open("interval1.txt", "r") as f_in:
        # Citim numărul de elemente și k
        n, k = map(int, f_in.readline().split())

        # Citim șirul de numere
        sir = list(map(int, f_in.readline().split()))

    # Găsim intervalul minim
    a, b = gaseste_interval_minim(sir, n, k)

    # Scriem rezultatul în fișierul de ieșire
    with open("interval1.txt", "w") as f_out:
        f_out.write(f"{a} {b}\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>

== Explicatie ==

Intervalul [8,9] conţine 3 elemente ale şirului – 8 9 9 şi are lungimea minimă. Există încă un interval cu aceeaşi lungime care conţine 3 elemente din şir – [9,10] elemente dar 8<9.