### PROBLEM LINK:

**Author:** Raghav Passi

**Testers:** Misha Chorniy

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

medium

### PREREQUISITES:

probability, expected value

### PROBLEM:

You are given a bag containing n balls, i-th of them having a volume of a_i. The probability of taking a ball is equal to its volume divided by the sum of volumes of all the bags in the bag.

### SOLUTION

Suppose you want to draw i-th ball. You randomly keep drawing the balls from the bag one by one till you draw the i-th ball. Find the expected number of turns required to draw i-th ball (for each i from 1 to n).

Expected number of turns required for i-th ball = 1 + expected number of balls drawn before the i-th ball.

Expected number of balls drawn before i-th ball can be found as the sum of the probability of j-th ball being drawn before the i-th ball (for each j \neq i).

Probability of j-th ball being drawn before the i-th will be \frac{a_j}{a_i + a_j}.

This the answer for i-th ball will be 1 + \sum\limits_{j=1, j\neq i}^{n} \frac{a_j}{a_i + a_j}

For a fixed i, this value can be calculated in \mathcal{O}(n) time. So, the overall time complexity of this program will be \mathcal{O}(n^2).

**Pseudo Code**

```
for (int i = 1; i <= n; ++i) {
double r = 1.0;
for (int j = 1; j <= n; ++j) {
if (j != i) {
r += 1.0 * a[j] / (a[i] + a[j]);
}
}
printf("%.6lf%c", (double)r, i == n ? '\n' : ' ');
}
```