11600 - Masud Rana

[battirunner]

i don't get the sample input output of this problem.... why the day is represented in fraction ? it'll be very helpful if anyone just enlighten it

[brianfry713]

Expected number of days can be a floating point. Read about probability.

[battirunner]

but how in this problem ? If you please explain just 2 sample input & output of the question ,, thanks in advance...

[brianfry713]

First sample input, on day 1 he will travel to either city 2 or 3. After that all cities are connected by safe roads.

Second sample input, After day 1 there is a 2 / 3 chance he will travel to city 2 or 3 - I will call this 1a, there is a 1 / 3 chance he will travel to city 4 - I will call this 1b.
E(0) = 1 + 2 / 3 * E(1a) + 1 / 3 * E(1b)

1a: Cities 1, 2, and 3 are connected, he is in city 1, 2, or 3. There is a 2 / 3 chance he will go to city 1, 2, or 3 (remember that he always chooses a new city other than the one he's staying in), There is a 1 / 3 chance he will go to city 4. If he travels to city 4 then all cities are connected, if he travels to city 1, 2, or 3 then we are in the same situation 1a.
E(1a) = 1 + 2 / 3 * E(1a)
Solving for E(1a) = 3

1b: Cities 1 and 4 are connected, also 2 and 3 are connected, he is in city 1 or 4. There is a 1 / 3 chance he will go to city 1 or 4, There is a 2 / 3 chance he will go to city 2 or 3. If he travels to city 2 or 3 then all cities are connected, if he travels to city 1 or 4 then we are in the same situation 1b.
E(1b) = 1 + 1 / 3 * E(1b)
Solving for E(1b) = 3 / 2

Solving for E(0) = 1 + 2 / 3 * 3 + 1 / 3 * 3 / 2 = 3.5