가족사진

앞에서 정신없는 가족 모임에 대해 이야기했다. 가장 정신없는 순간 중 하나는 보통 가족사진을 찍으려 할 때다. 두 살배기가 카메라를 보게 하려면 어떻게 해야 하는가? 그리고 왜 사진을 찍으려는 바로 그 순간에 재채기를 해야 하는 사람이 항상 적어도 한 명은 있는가? 누가 어디에 서야 하는지 정하는 것도 어렵기는 마찬가지다. 여기서는 사람들을 사진에 배치하는 것을 돕는 프로그램을 작성한다. 모두가 한 줄로 서 있는 사진만 생각한다. 사진사는 여자들이 설 순서와 남자들이 설 순서를 이미 정했다. 문제는 두 성별을 어떻게 섞을지다. 목표가 두 가지 있다. 성별을 고르게 흩어 놓는 것, 그리고 이웃한 사람 사이의 키 차이를 작게 유지하는 것이다. 두 목표는 서로 충돌할 수 있으니 계산할 것이 좀 있다.

여자 w명 각각에 대해 설 순서대로 키 hi가 주어지고, 남자 m명에 대해서도 마찬가지로 주어진다. 남자가 더 많을 때도 있고 여자가 더 많을 때도 있다. 이 예에서는 w ≥ m이라고 하자. 그러면 남자들이 m + 1개의 구간을 정하고, 평균적으로 이 구간 각각에 w/(m+1)명의 여자가 있어야 한다. (m ≥ w이면 성별을 바꾸어 마찬가지로 한다.) 물론 w/(m+1)이 정수가 아닐 수 있는데, 이 경우 m + 1개의 구간 중 어느 구간에 ⌈w/(m+1)⌉명의 여자를 넣고 어느 구간에 ⌊w/(m+1)⌋명의 여자를 넣을지는 전적으로 자유다.

이 등간격 제약 아래에서 다음과 같이 측정되는 "키 편차"를 최소화해야 한다. 왼쪽에서 j번째 자리에 선 사람을 pj라 하고, 그 사람의 키를 hpj라 하자. 그러면 총 키 편차는 Σ(hpj+1 − hpj)2이다.

첫 줄은 입력 데이터 세트의 수 K이고, 그다음에 K개의 데이터 세트가 각각 다음과 같은 형태로 주어진다.

데이터 세트의 첫 줄에는 두 정수 1 ≤ w, m ≤ 500이 있다. 다음 줄에는 0과 1000 사이의 정수 w개가 있으며, 여자 w명의 키를 설 순서대로 나타낸다. 그다음 줄에는 0과 1000 사이의 정수 m개가 있으며, 남자 m명의 키를 설 순서대로 나타낸다.

각 데이터 세트마다 "Data Set x:"를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호다. 그다음 줄에 등간격 제약 아래에서 얻을 수 있는 최소 총 키 편차를 출력한다.

각 데이터 세트 뒤에는 빈 줄을 출력한다.