P6069 "MdOI R1" Group

The testdata for this problem was used during the contest. But later, yummy felt it was unnecessary, so the strengthening was abandoned. **There is a solution that does not use `long double` or `__int128`.**

To make the members of our team more united, we want everyone’s skill level to be as balanced as possible. At this time, someone needs to make some changes to themselves. Our team has $n$ students. The skill value of the $i$-th student is an integer $a_i$. We consider the team to be united when the **variance** of the whole group’s skill values is **no more than $m$**. What is the minimum number of students who must change their skill values (they may change them to any **real number**) so that the team can become united? To avoid precision errors when reading input, the given $m$ is **$n$ times the real value**, and this value is an integer. --- If you do not know what variance is, here is the basic concept: Variance is an indicator that measures how much a set of data **fluctuates**. Let the average of a sequence $a_{1\dots n}$ of length $n$ be $p$. Then the variance $S$ of this sequence is: $$ S=\frac{1}{n} \sum_{i=1}^n(a_i-p)^2 $$

The first line contains integers $n,m$, representing the number of students and $n$ times the upper limit of the variance. The second line contains $n$ integers $a_{1\cdots n}$, representing each student’s skill value.

The first line contains an integer $t$, representing the minimum number of people whose skill values must be changed.

[Sample 1 Explanation] In this sample, $n=4$, and the real $m=\dfrac{32}{n}=8$. At the beginning, the average of all students’ skill values $a_i$ is $1$, and the variance is: $$S=\dfrac{1}{4}[(3-1)^2+(7-1)^2+(-5-1)^2+(-1-1)^2]=20$$ After changing the 3rd student’s skill value to $3$, the average becomes $3$, and the variance is: $$S=\dfrac{1}{4}[(3-3)^2+(7-3)^2+(3-3)^2+(-1-3)^2]=8$$ Only $1$ person’s skill value was changed, which meets the requirement. [Sample 2 Explanation] In this sample, $n=5$, and the real $m=\dfrac{18}{n}=3.6$. At the beginning, the average of all students’ skill values $a_i$ is $4.6$, and the variance is $7.44$: After changing the 5th student’s skill value to $3.5$, the average becomes $3.5$, and the **variance is $2.6$.** Only $1$ person’s skill value was changed, which meets the requirement. --- [Constraints] | Subtask ID | $n\leq$ | Points | | :-: | :-: | :-: | | 1 | $16$ | 15 | | 2 | $300$ | 17 | | 3 | $10^3$ | 20 | | 4 | $5\times 10^3$ | 7 | | 5 | $10^4$ | 8 | | 6 | $2\times 10^5$ | 33 | For all test points, $1\leq n\leq 2\times 10^5$, $1\leq m\leq 10^{18}$, and $0\leq |a_i|\leq 10^6$. Translated by ChatGPT 5