Праведна подела чоколадица
време | меморија | улаз | излаз |
---|---|---|---|
0,1 s | 64 Mb | стандардни излаз | стандардни улаз |
Дато је \(n\) пакета чоколаде и за сваки од њих је познато колико чоколадица садржи. Сваки од \(k\) ученика узима тачно један пакет, при чему је циљ да сви ученици имају што приближнији број чоколадица. Колика је најмања могућа разлика између оног ученика који узме пакет са најмање и оног који узме пакет са највише чоколадица.
Улаз
Са стандардног улаза се уноси природан број \(n\) (\(1 \leq n \leq 50000\)) а затим и \(n\) природних бројева (између \(1\) и \(10^6\), раздвојене са по једним размаком) који представљају број чоколадица у сваком пакету. У последњем реду се уноси број деце \(k\) (\(1 \leq k \leq n\)).
Излаз
На стандардни излаз исписати вредност најмање разлике.
Пример
Улаз
8 3 8 1 17 4 7 12 9 4
Излаз
5
Најмања разлика се добија ако деца узму пакете са 8, 4, 7 и 9 чоколадица.
Морате бити улоговани како бисте послали задатак на евалуацију.