102911: [Atcoder]ABC291 B - Trimmed Mean

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of $5N$ judges grades Takahashi's performance, and his score is determined as follows:

• Invalidate the grades given by the $N$ judges who gave the highest grades.
• Invalidate the grades given by the $N$ judges who gave the lowest grades.
• Takahashi's score is defined as the average of the remaining $3N$ judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades $S$ ($|S|=5N$):

• Repeat the following operation $N$ times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from $S$.
• Repeat the following operation $N$ times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from $S$.
• Takahashi's score is defined as the average of the $3N$ elements remaining in $S$.

The $i$-th $(1\leq i\leq 5N)$ judge's grade for Takahashi's performance was $X_i$ points. Find Takahashi's score.

Constraints

• $1\leq N\leq 100$
• $0\leq X_i\leq 100$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$
$X_1$ $X_2$ $\ldots$ $X_{5N}$

Output

Print Takahashi's score.
Your answer will be considered correct if the absolute or relative error from the true value is at most $10^{-5}$.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since $N=1$, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The $2$-nd judge gave the highest grade ($100$ points), which is invalidated.
Additionally, the $1$-st judge gave the lowest grade ($10$ points), which is also invalidated.
Thus, the average is $\displaystyle\frac{20+50+30}{3}=33.333\cdots$.

Note that the output will be considered correct if the absolute or relative error from the true value is at most $10^{-5}$.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since $N=2$, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The $10$-th and $9$-th judges gave the highest grades ($100$ and $99$ points, respectively), which are invalidated.
Three judges, the $1$-st, $2$-nd, and $3$-rd, gave the lowest grade ($3$ points), so two of them are invalidated.
Thus, the average is $\displaystyle\frac{3+4+5+6+7+8}{6}=5.5$.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.

问题描述

高桥正在参加一个体操比赛。

在这个比赛中，$5N$名评委对高桥的表现进行评分，他的分数是这样确定的：

• 取消给分最高的$N$名评委的评分。
• 取消给分最低的$N$名评委的评分。
• 高桥的分数定义为剩余$3N$名评委评分的平均值。

更正式地说，高桥的分数是通过以下过程获得的：对评委评分集合$S$（$|S|=5N$）进行以下操作：

• 重复以下操作$N$次：选择最大的元素（如果有多个这样的元素，选择其中一个）并从$S$中删除它。
• 重复以下操作$N$次：选择最小的元素（如果有多个这样的元素，选择其中一个）并从$S$中删除它。
• 高桥的分数定义为$S$中剩余$3N$个元素的平均值。

第$i$个（$1\leq i\leq 5N$）评委给高桥的表演打分为$X_i$分。 找出高桥的分数。

约束条件

• $1\leq N\leq 100$
• $0\leq X_i\leq 100$
• 输入中的所有值都是整数。

输入

输入是通过标准输入以以下格式给出的：

$N$
$X_1$ $X_2$ $\ldots$ $X_{5N}$

输出

打印高桥的分数。
如果与真实值的绝对误差或相对误差不超过$10^{-5}$，则答案将被认为是正确的。

样例输入1

1
10 100 20 50 30

样例输出1

33.333333333333336

由于$N=1$，给分最高的评委的评分和给分最低的评委的评分将被取消。
第$2$个评委给出的分数最高（$100$分），被取消。
此外，第$1$个评委给出的分数最低（$10$分），也被取消。
因此，平均分为$\displaystyle\frac{20+50+30}{3}=33.333\cdots$。

注意，如果与真实值的绝对误差或相对误差不超过$10^{-5}$，则输出将被认为是正确的。

样例输入2

2
3 3 3 4 5 6 7 8 99 100

样例输出2

5.500000000000000

由于$N=2$，给分最高的$2$名评委的评分和给分最低的$2$名评委的评分将被取消。
第$10$名和第$9$名评委给出的分数最高（分别是$100$分和$99$分），被取消。
第$1$名、第$2$名和第$3$名评委给出的分数最低（都是$3$分），其中的$2$名将被取消。
因此，平均分为$\displaystyle\frac{3+4+5+6+7+8}{6}=5.5$。

注意，从最低$3$名评分的评委中选择取消$2$名评分的评委的选择不会影响答案。