imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:52Z

New page

[http://acm.uva.es/p/v102/10271.html 원문보기]
----
=== 이 문제는 ===
인기도: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 ===
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 ===
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

=== 풀이 ===
{| class="wikitable"
|-
| 작성자
| 사용언어
| 개발시간
| 코드
|-
| 문보창
| C++
| 4시간
| [[Chopsticks/문보창]]
|}

=== 쓰레드 ===
----
[[문제분류]] / [[경시대회준비반]]

Chopsticks - Revision history

imported>Unknown at 05:22, 7 February 2021