시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 28 | 22 | 22 | 78.571% |
Rikka is a talented student.
She likes to wander in the corridor while solving ICPC problems. Specifically, she will do a random walk for $n$ steps. In the $i$-th random step, she will choose one of the vectors $(x, y)$ such that $x, y \in \mathbb{R}$ and $x^2 + y^2 \le R_i^2$ with equal probability. And then she will walk along the vector. In other words, if she stood at $(A, B)$ before the random step, she will stand at $(A + x, B + y)$ afterwards. Before wandering, she stands at the door $(0, 0)$.
After wandering, she was curious about the expectation of the square of Euclidean distance to point $(0, 0)$. In other words, she wants to know the expected value of $x^2 + y^2$, if she stands at $(x, y)$ after all $n$ random steps.
The first line contains an integer $n$, the number of random steps.
The second line contains $n$ positive integers $R_i$, the parameter of the $i$-th random step.
It is guaranteed that $1 \le n \le 50\,000$ and $1 \le R_i \le 1000$.
You need to output $d$, the expected value of $x^2 + y^2$. Assuming the correct result is $d^*$, you need to ensure that $\frac{|d - d^*|}{\max\{d^*, 1\}} \leq 10^{-6}$.
3 1 2 3
7.000000000000000