Cerinţa
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.in
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 ieşire
Fişierul de ieşire interval1.out
va conţine pe prima linie două numere a
şi b
, separate printr-un spaţiu, cu semnificaţia de mai sus.
Restricţii şi precizări
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 carea
este minim a ≤ b
Exemplu:
interval1.in
10 3 11 9 3 2 8 11 9 10 15 13
interval1.out
8 9
Explicație
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
.