중앙값

중앙값은 자료를 늘어놓았을 때 한가운데에 오는 값이다. 중앙값보다 작은 자료의 개수와 큰 자료의 개수가 서로 같다.

자료 전체를 $d_1, d_2, d_3, \dots, d_n$이라고 하자.

$n$이 홀수이면 중앙값은 $(n+1)/2$번째 자료다.

$\text{Median} = d_{(n+1)/2}$

$n$이 짝수이면 중앙값은 $n/2$번째 자료와 $n/2+1$번째 자료의 평균이다.

$\text{Median} = \frac{d_{n/2} + d_{n/2+1}}{2}$

자료의 위치는 입력에 적힌 순서를 그대로 따른다. 자료를 다시 정렬하지 않는다.

각 줄에 자료 묶음이 하나씩 주어진다. 줄의 첫 번째 정수는 그 묶음에 든 자료의 개수 $n$이고, 이어서 자료 $n$개가 나온다. 자료 값은 $1$ 이상 $10^6$ 이하의 정수다. 입력은 100줄 이하이고, 한 줄에 오는 자료는 100개 이하다. 마지막 줄에는 0 하나만 주어지며, 이 줄이 입력의 끝이다.

자료 묶음마다 중앙값을 한 줄에 하나씩, 입력에 나온 순서대로 출력한다. 각 줄은 Case n:으로 시작하고, 콜론 뒤에 공백을 하나 둔 다음 중앙값을 적는다. $n$은 1부터 세는 묶음 번호다. 중앙값은 소수점 아래 한 자리까지 출력한다.