멘델의 유전학

오스트리아의 수도사 그레고어 멘델(1822–1884)은 유전형 유전 이론을 개척하여 유전학의 창시자로 불린다. 이 문제에서는 멘델의 완두콩 교배 실험을 더 빠르게 처리하도록 돕는다.

완두콩의 여러 특성 중 크기 하나만 고려한다. 각각 크기를 가진 $n$개의 초기 품종에서 시작하면, 두 품종을 짝지어 교배해 한 세대 뒤에는 $n^2$가지의 교배종을 얻는다. 멘델은 더 큰 완두콩을 얻고 싶지만 자원이 부족하여 $n^2$개의 후보 중 오직 $n$개만 재배할 수 있으므로, 가장 유망한 $n$개를 골라야 한다.

숨겨진 유전형을 알 수 없으므로, 크기가 $x$와 $y$인 두 부모로부터 나오는 교배종의 크기는 다음 식으로 추정한다.

$\left\lceil \frac{x + y}{2} \right\rceil$

예를 들어 두 부모의 크기가 $5$와 $2$이면 교배종의 크기는 $\lceil 7/2 \rceil = 4$로 추정한다.

$n \times n$ 조합으로 이루어진 행렬에서 가장 큰 $n$개의 값을 구하여라. 한 품종을 자기 자신과 교배하는 경우, 즉 대각선 원소도 포함한다.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 각각 다음 형식으로 주어진다.

• 첫째 줄에 초기 품종의 개수 $n$ ($1 \le n \le 10000$)이 주어진다.
• 둘째 줄에 초기 품종들의 크기를 나타내는 $n$개의 양의 정수가 주어진다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호(1부터 시작)이다. 다음 줄에는 $n \times n$ 조합 행렬에서 가장 큰 $n$개의 수를 내림차순으로 정렬하여 공백 하나로 구분해 출력한다. 서로 이웃한 데이터 집합 사이는 빈 줄 하나로 구분한다.