| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 5 | 5 | 4 | 100.000% |
Arash har nu kommit hem från onsite-finalen i Linköping och är tillbaka i vardagen. Nu har han precis kommit hem från ett tvättstugebesök och ska återigen matcha strumpor. När han nu sitter där med sina $N$ strumpor så känner han att han bara behöver $K$ par strumpor, resten kan få förbli osorterade. Det är alltså okej om $N-2K$ strumpor förblir omatchade, tänker Arash.
Varje strumpa en färg $F_i$. Två strumpor $i$ och $j$ kan paras ihop om skillnaden i färg strikt understiger heltalet $D$ d.v.s. $|F_{i} - F_{j}|<D$. Men istället för att hjälpa Arash matcha så många strumpor som möjligt så ska du hjälpa honom att hitta det minsta möjliga $D$ så att han kan matcha minst $K$ strumppar!
Indata består av en rad med de två heltalen $N$ och $K$ ($2 \le N \le 50\,000$, $2 \le 2K \le N$).
Därefter följer en rad med $N$ heltal: $F_1, F_2, \dots, F_N$. Talen $F_i$ ligger mellan $1$ och $10^{15}$ (inklusive).
Du ska skriva ut ett enda heltal: den minimala differens $D$ som gör att Arash kan matcha minst $K$ strumppar med varandra.
5 2 3 8 1 5 9
3
4 1 100 101 102 103
2
10 4 81 92 42 45 62 5 4 85 73 22
9
2 1 1000000000000 5000000000000
4000000000001
Olympiad > Swedish Olympiad in Informatics > 2014 > KATT A번