### Re: 11600 - Masud Rana

Posted:

**Thu Dec 25, 2014 1:55 pm**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

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=51&t=208156

Page **1** of **1**

Posted: **Thu Dec 25, 2014 1:55 pm**

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

Posted: **Tue Jan 06, 2015 5:42 am**

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

Posted: **Fri Jan 09, 2015 11:08 am**

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

Posted: **Fri Jan 09, 2015 10:15 pm**

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

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