Problem E
Erosion Filter
One useful tool in image processing is applying filters to images. They can be used to remove noise, sharpen images, and many other things.
In this problem, let’s experiment with a new custom filter called the erosion filter. It takes in an image, then, for each pixel, the new value is the weighted average of the values of all the pixels in the image based on their distance.
To simplify this further, let’s just work with a one-dimensional array of integers instead of an image. Suppose we have an array $A$ with $n$ elements, and we want to apply the erosion filter to it. The new array $B$ is computed as follows:
\[ B[i] = \sum _{j=1}^{n} \frac{A[j]}{2^{|i - j|}} \]Informally, the value of $B[i]$ is the weighted average of the values of all the elements in $A$, with the elements closer to $i$ having a much greater effect.
Right now, we have this array $A$ with $n$ elements and you want to apply the erosion filter to it. The next step is to implement an algorithm to compute $B$!
Your answer will be considered correct if each value $B[i]$ that you computed is within $10^{-5}$ of the correct value.
Input
The first line of input contains one integer $n$, the number of elements in the array $A$ ($1 \leq n \leq 100\, 000$).
The next line of input contains $n$ integers, the values of the pixels in the image $A$ ($1 \leq A[i] \leq 10^{9}$).
Output
You should output a line containing $n$ floating-point numbers, the values of the pixels in the image $B$. Your answer is considered correct if the absolute error of each value is at most $10^{-5}$. In other words, if the correct value is $x$ and your answer is $y$, then $|x - y| \leq 10^{-5}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 7 9 |
10.75 14 13.75 |
