410417: GYM104020 A Adjusted Average

As a student of the Biology And Probability Course at your university, you have just performed an experiment as part of the practical assignments. However, your results do not look very nice: you had hoped that the average of your samples would be different from what it is now.

To improve your results, you decide to let some of your samples "magically disappear" (i.e., dump them in the waste bin). In order to not raise suspicion with your teacher, you can remove only a few of your samples. How close can you possibly get to your desired average?

The input consists of:

• One line with three integers $$$n$$$, $$$k$$$, and $$$\overline{x}$$$ ($$$2 \leq n \leq 1500$$$, $$$1 \leq k \leq 4$$$, $$$k < n$$$, $$$\left| \overline{x} \right| \leq 10^9$$$), the number of samples, the number of samples that may be removed, and the average you think looks the nicest.
• One line with $$$n$$$ integers $$$x$$$ ($$$\left| x \right| \leq 10^9$$$), representing the samples.

Output the minimal absolute difference between $$$\overline{x}$$$ and the average you can obtain by removing at most $$$k$$$ samples from the dataset.

Your answer should have an absolute error of at most $$$10^{-4}$$$.

5 2 2
1 2 3 100 200

0.00000000000000000000

5 4 -5
-6 -3 0 6 3

0.50000000000000000000

4 1 4
1 3 3 7

0.33333333333333333326