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 '''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 &les; k &les; n &les; 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

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


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