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

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

# 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()))

# Apelare funcție
rezultat = gaseste_interval(n, k, sir)

# Scriere în fișierul de ieșire
with open('interval1out.txt', 'w') as file:
    file.write(f"{rezultat[0]} {rezultat[1]}")

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

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.