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(n, k, sir):

   index_start = 0
   index_end = k - 1
   sir.sort()

   lungime_minima = sir[index_end] - sir[index_start]
   interval_minim = (sir[index_start], sir[index_end])

   for i in range(1, n - k + 1):
       lungime_curenta = sir[i + k - 1] - sir[i]
       if lungime_curenta < lungime_minima:
           lungime_minima = lungime_curenta
           index_start = i
           index_end = i + k - 1
           interval_minim = (sir[index_start], sir[index_end])

   return interval_minim

1. Citire din fișierul de intrare

with open('interval1i.txt', 'r') as file:

   n, k = map(int, file.readline().split())
   sir = []
   for _ in range(n):
       sir.extend(map(int, file.readline().split()))

1. Apelare funcție

rezultat = gaseste_interval(n, k, sir)

1. Scriere în fișierul de ieșire

with open('interval1out.txt', 'w') as file:

   file.write(f"{rezultat[0]} {rezultat[1]}")

1. Verificare restrictii

assert 1 <= k <= n <= 1000 assert all(-1000 <= x <= 1000 for x in sir)

</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.