Informatica Online Judge

  출력 전력 차이 최소화 [2294 / 08F6]

Time Limit(Test case) : 4000(ms)
Number of users who solved : 11   Total Tried : 15


The Champion of this Problem (C++) : gs17082 - ms / 674byte
My Best Submission (C++) : N/A

[ACM ICPC 2013 WF]

Background

신형 CPU들을 만들어 여러 대의 장비에 설치해 판매하고 있다. CPU를 만드는 것은 쉽지만, CPU에 전기를 공급시키기 위해 필요한 배터리들이 출력이 다르기 때문에, 각 장비에 장착된 CPU들에 어떤 배터리들을 어떻게 연결할 지는 어렵다.

n대의 장비가 있고, 각 장비에는 2개씩의 CPU가 장착되어있으며, 각각의 CPU에는 k개의 배터리가 연결되어야 한다.

어떤 CPU에 k개의 배터리가 연결되면, 그 CPU를 통해서 다시 전력이 출력되는데, 그 CPU의 출력 값은 k개의 배터리 출력 중에서 가장 작은 값이 된다. 예를 들어 1, 3, 5 출력의 배터리가 CPU에 연결되면 CPU에서 출력되는 전력은 1이 된다.

한 장비에 설치된 두 CPU의 출력이 비슷하면 비슷할수록 장비는 더 잘 동작하기 때문에, 한 장비에 설치되어있는 두 CPU에서 출력되는 전력을 최대한 비슷하게 만들어야 한다. 그리고 n대의 장비 각각에 설치되어있는 두 CPU 의 출력 차이를 최소화해야 한다.

$2nk$ 개의 배터리와 그 전력이 주어질 때, $n$대의 장비에서 출력되는 CPU 출력 차이를 최소화 할 수 있는 값을 찾아보자.

예를 들어, $2$대의 장비가 있고, 각 장비의 CPU들에는 $3$개씩의 배터리들이 필요하고, $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$ 만큼의 전력을 공급할 수 있는 배터리들이 주어진다면, $[1, 3, 5], [2, 4, 12]$ 의 조합으로 첫 번째 장비에 연결하고, $[6, 8, 9]$, $[7, 10, 11]$ 의 조합으로 두 번째 장비에 연결하면, 각 CPU에서 출력되는 전력은 $(1, 2)$, $(6, 7)$이 되고, 두 장비 모두 두 CPU 의 출력 차이를 $1$로 최소화 시킬 수 있다. 다른 조합 방법도 있다.

Input

첫 번째 줄에는 장비의 대수($n$)와 각 CPU에 연결되어야하는 배터리 수($k$, $2nk ≤10^6$)가 공백을 두고 입력된다.

두 번째 줄에는 $2nk$개 배터리 각각의 출력 전력($p_i$)이 공백을 두고 입력된다.($1≤ p_i ≤10^9$)

Output

n대의 장비에 있는 CPU들에 배터리들을 연결한다고 할 때, CPU 출력 차이의 최댓값을 최소화 할 수 있는 값을 출력한다.

IO Example

2 3
1 2 3 4 5 6 7 8 9 10 11 12

출력1
1

입력2
2 2
3 1 3 3 3 3 3 3

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]