E D R , A S I H C RSS

Chopsticks

이 문제는

인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)

About Chopsticks

중국에서는 음식을 먹을 때 젓가락 두 개를 쓰지만, L씨는 조금 다르다. 그는 젓가락 세 개를 사용한다. 셋 중 하나는 긴 젓가락으로, 음식을 쿡 찍어먹기 위한 용도로 쓰인다. 두 개의 일반 젓가락의 길이는 최대한 비슷해야 하지만 나머지 하나는 무조건 제일 길기만 하면 된다. 길이가 각각 A, B, C(A<=B<=C)인 세 개의 젓가락이 있을 때 (A-B)^2을 계산하면 두 젓가락이 짝이 안 맞는 정도를 구할 수 있다.

L씨는 그의 생일 파티에 K명의 손님을 초대했는데, 그의 특이한 젓가락질 방법을 소개하고 싶어서 안달이 나 있다. 젓가락을 K+8세트(L씨 자신, 부인, 아들, 딸, 어머님, 아버님, 장모님, 장인어른, 그리고 K명의 손님)를 준비해야 한다. 하지만 L씨네 집에 있는 젓가락들 중에는 길이가 다른 것이 많다. 젓가락들의 길이가 주어졌을 때, 각 세트의 짝이 안 맞는 정도를 최소화하면서 K+8세트를 만들어내는 방법을 찾아야 한다.

Input

첫째 줄에는 테스트 케이스의 개수를 나타내는 정수 T(1<=T<=20)가 입력된다. 각 테스트 케이스의 첫째줄에는 손님 수를 나타내는 정수(0<=K<=1,000)와 젓가락의 개수를 나타내는 정수 N(3K+24<=N<=5,000)이 입력된다. 그 밑으로는 각 젓가락의 길이를 나타내는 N개의 양의 정수 Li(1 <= Li <= 32,000)가 오름차순으로 입력된다.

output

입력된 각 테스트 케이스에 대해 한 줄에 하나씩, 모든 젓가락 세트의 짝이 안 맞는 정도의 합이 가지는 최소 값을 출력한다.

Sample Input

~cpp 
1
1 40
1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164

Sample Output

~cpp 
23

Note

위의 입력 예에 대해서 다음과 같은 식으로 젓가락 세트를 구성할 수 있다.
8,10,16 ; 19,22,27; 61,63,75; 71,72,88; 81,81,84; 96,98,103; 128,129,148; 134,134,139; 157,157,160

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 4시간 Chopsticks/문보창

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0892 sec