Problem F
X-ray spectrum
When simulating x-ray imaging different energy photons interact differently and therefore needs to be simulated separetly. Often one has an x-ray spectrum with thousands of bins, so that it is impractical to do a simulation for each bin. We want to do simulations only for a few energies, but want to choose these energies in an optimal way. Energies for the simulation should be chosen to minimize the sum over all photons of the square of the distance between the energy of that photon and its closest simulation energy.
Input
The input will start with two integers $1\leq n\leq 200$ and $1\leq m \leq n$ denoting the number of energies in the input spectrum and the number of simulation energies, respectively. This is followed by a line of $n$ integers $0\leq k_ i\leq 10^6$, where $k_ i$ ($1\leq i \leq n$) is the number of photons with energy $i$ in the x-ray spectrum. Simulation energies $E_ j$ ($1\leq j \leq m$) should be selected so as to minimize
\[ \sum _{i=1}^ n k_ i\min _ j\left((i-E_ j)^2\right). \]Output
Output one number, the minimum value of the sum above, with a relative or absolute error less than $10^{-4}$.
Example
In sample input 1 we are have $n=3$, $m=2$, $k_1=3$, $k_2=1$, and $k_3=1$. Optimal simulation energies will be $E_1=1$ and $E_2=2.5$, since this will remove the contribution from bin 1 and minimize the contribution from bins 2 and 3. The sum will be $k_1(1-E_1)^2+k_2(2-E_2)^2+k_3(3-E_2)^2=3\cdot 0^2+1\cdot 0.5^2+1\cdot 0.5^2=0.5$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 3 1 1 |
0.5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 8 0 5 13 2 |
6.55 |
