#GYM104651D. Discrete Fourier Transform
Discrete Fourier Transform
Description
Given a sequence of integer $f_0, f_1, \ldots, f_{n-1}$, the discrete Fourier transform gives a sequence of complex numbers $F_0, F_1, \ldots, F_{n-1}$ that
$$ F_t = \sum_{s=0}^{n-1} f_s\ e^{-2 \pi i s t / n}$$
for each $t=0,1,\ldots,n-1$, where $e^{i\theta} = \cos \theta + i \sin \theta$, and $i$ is the imaginary unit that $i^2=-1$.
You may reset $f_k$ to any integer value to minimize the maximum value among $|F_0|, |F_1|, \ldots, |F_{n-1}|$, where $|z|=|p+qi|=\sqrt{p^2+q^2}$ $(p, q \in \mathbb{R})$ is the modulus of the complex number $z$.
The first line contains two integers $n$ ($1 \leq n \leq 2\,000$) and $k$ ($0 \le k < n$).
The second line contains $n$ integers $f_0, f_1, \ldots, f_{n-1}$ ($-2\,000 \le f_i \le 2\,000$).
Output a line containing a single real number, indicating the minimum of the maximum value among $|F_0|, |F_1|, \ldots, |F_{n-1}|$ after resetting $f_k$ to any integer value.
Your answer is acceptable if its absolute or relative error does not exceed $10^{-9}$. Formally speaking, suppose that your output is $a$ and the jury's answer is $b$, your output is accepted if and only if $\frac{|a - b|}{\max\{1, |b|\}} \leq 10^{-9}$.
Input
The first line contains two integers $n$ ($1 \leq n \leq 2\,000$) and $k$ ($0 \le k < n$).
The second line contains $n$ integers $f_0, f_1, \ldots, f_{n-1}$ ($-2\,000 \le f_i \le 2\,000$).
Output
Output a line containing a single real number, indicating the minimum of the maximum value among $|F_0|, |F_1|, \ldots, |F_{n-1}|$ after resetting $f_k$ to any integer value.
Your answer is acceptable if its absolute or relative error does not exceed $10^{-9}$. Formally speaking, suppose that your output is $a$ and the jury's answer is $b$, your output is accepted if and only if $\frac{|a - b|}{\max\{1, |b|\}} \leq 10^{-9}$.
3 2
1 1 0
2.0