### PROBLEM LINK:

**Author:** Anurag Anand

**Tester:** Sameer Gulati

### DIFFICULTY:

EASY

### PREREQUISITES:

DP, Probabilites

### PROBLEM:

You are given a game with **N** levels. The time taken and the probability of passing a level is given. You need to find the expected time taken to pass all the levels.

### EXPLANATION:

Let E_i be the expected time taken to pass all the levels till i.

E_0 = 0. Let us consider level i > 0.

We can write E_i = E_{i-1} + T_i where T_i is the expected time taken to pass level i.

Let us consider two cases at level i:

- He passes the level: Expected time taken = p_it_i.
- He fails the level: Expected time taken = (1-p_i)(t_i + E_i). This is because he’ll have to start again from the first level and pass all the levels till i again.

T_i = p_it_i + (1-p_i)(t_i + E_i) = t_i + (1-p_i)E_i.

Hence, E_i = E_{i-1} + t_i + (1 - p_i)E_i

i.e. E_i = \frac{E_{i-1} + t_i}{p_i}

### AUTHOR’S SOLUTION:

Author’s solution can be found here.