Start

2019-10-17 18:00 CEST

Dagy Svår Tävling 1

End

2019-10-24 18:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -414 days 5:17:24

Time elapsed

168:00:00

Time remaining

0:00:00

Problem A
Strumpmatchning 2

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.

Som i uppgiften strumpmatchning så har 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

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 $1\, 000\, 000\, 000\, 000\, 000$ (inklusive).

Utdata

Du ska skriva ut ett enda heltal: den minimala differens $D$ som gör att Arash kan matcha minst $K$ strumppar med varandra.

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

  • För $40$ poäng så kommer $N$ vara maximalt $200$ och varje färg maximalt $5\, 000$.

  • För ytterligare $30$ poäng så kommer $N$ vara maximalt $1\, 000$.

Sample Input 1 Sample Output 1
5 2
3 8 1 5 9
3
Sample Input 2 Sample Output 2
4 1
100 101 102 103
2
Sample Input 3 Sample Output 3
10 4
81 92 42 45 62 5 4 85 73 22
9
Sample Input 4 Sample Output 4
2 1
1000000000000 5000000000000
4000000000001