Problem

**Author:** Rishav Pati

**Tester:** Rajat De

**Editorialist:** Rishav Pati

### DIFFICULTY:

EASY

### QUICK EXPLANATION:

Direct application of gambler’s ruin. I was unaware of the topic while setting the question. Can be also solved by writing equations for all states in the game and finding pattern.

### EXPLANATION

Let P_0,P_1, … P_{n+m} be the expected no. of turns if the 1st plater has 0,1 … n+m coins.

Clearly,

P_0 = P_{n+m}, P_1 = P_{n+m-1} and so on.

Now we know that P_0 = P_{n+m} = 0.

For 1 <= i < n+m, we can write,

P_i = (P_{i-1} + P_{i+1})/2.

Using this and the fact that P_{i} = P_{n+m-i},

We can easily obtain every P_i by substitution.

It can be observed that P_i = i*(n+m-i).