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 interval1i.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 interval1out.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

interval1in.txt

10 3

11 9 3 2 8 11 9 10 15 13

interval1out.txt

Datele introduse corespund restrictiilor impuse

8 9

Exemplul 2

interval1in.txt

4 2

20,5,100,75.2

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.