No.3632 IQR
タグ : / 解いたユーザー数 53
作問者 : 👑
ssmbc2929_bartok
/ テスター :
👑 
p-adic
Problem Statement
There are $N$ students at the school Baru attends.
One day, the teachers decided to investigate how much the standing long jump records vary.
However, a certain number of the students at this school are non-human creatures such as youkai, and on top of that, everyone is said to start fooling around right away.
Therefore, since there is a good chance that outliers are mixed into the records, they decided to remove the outliers using the IQR method.
The IQR method is one of the techniques for determining outliers.
When the interquartile range $\mathrm{IQR}$ is defined by $Q_3 - Q_1$,
a value $x$ is regarded as an outlier if $x < Q_1 - 1.5 × \mathrm{IQR}$ or $x > Q_3 + 1.5 × \mathrm{IQR}$ holds; in that case, $x$ is an outlier.
You are given the total number of students $N$ and each student's record $A_1, A_2, ..., A_N$.
Output the quartiles $Q_1$, $Q_2$, $Q_3$ obtained from these records and the number of outliers $U$.
Here, the first quartile is denoted by $Q_1$, the second quartile by $Q_2$, and the third quartile by $Q_3$.
Definition of quartiles
The median of data consisting of $n$ values is defined as follows.
- If $n$ is odd: the middle value when sorted in ascending order
- If $n$ is even: the average of the middle $2$ values when sorted in ascending order
Then, the quartiles are defined as follows.
- The median of the entire data is the second quartile $Q_2$.
- The median of the smallest $\left\lfloor \frac{N}{2} \right\rfloor$ values of the data is the first quartile $Q_1$.
- The median of the largest $\left\lfloor \frac{N}{2} \right\rfloor$ values of the data is the third quartile $Q_3$.
Constraints
- $3 \le N \le 4 × 10^5$
- $5 \le A_i \le 10^9$
- All inputs are integers.
Input
$N$ $A_1\ A_2\ ...\ A_N$
Output
$Q_1$ $Q_2$ $Q_3$ $U$
Output the quartiles and the number of outliers in the order $Q_1, Q_2, Q_3, U$ on a single line, separated by single-byte spaces.
Print a newline at the end.
Your answer is judged correct if its absolute error or relative error from the true answer is at most $10^{-6}$.
However, due to the judge's constraints, your output must be fewer than $500$ digits.
Also, due to the judge's specifications, if you output $0$, correctness is judged by absolute error only.
Sample
Sample 1
Input
5 60 75 90 56 46
Output
51.0 60.0 82.5 0
$Q_1$ is $51$, $Q_2$ is $60$, and $Q_3$ is $82.5$.
Since the interquartile range is $31.5$, the lower limit for not being an outlier is $51 - 31.5 × 1.5 = 3.75$,
and the upper limit is $82.5 + 31.5 × 1.5 = 129.75$.
There are no outliers in this case. Therefore, outputting $0$ at the end is correct.
Note that outputting $51$ in place of $51.0$, or $0.0$ in place of $0$, and so on, is also accepted.
Sample 2
Input
10 270 300 53 319 249 600 213 250 310 725
Output
249.0 285.0 319.0 3
Note that the quartiles must be computed "with the outliers included".
Sample 3
Input
7 30 30 30 30 30 30 30
Output
30 30 30 0
All elements of $A$ may be the same.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。