John is locked in a mansion that is shaped like a star, with a number of corridors of distinct length that meet at a common point in the center. He is desperately looking for an exit, so he wants to check the end of every corridor to see if he can find one.
He is initially at the outer end of one of the corridors. In his desperation, he does not develop a good strategy, and instead, decides to do the following: He will run to the center, and when he gets there, he will randomly enter a different corridor than the one he came from. He will then run to the outer end of that corridor, turn back, and return to the center, where he will again randomly enter a different corridor than the one he just came from (but possibly a corridor he was in before that). He will repeat this process until he has visited the outer ends of all the corridors at least once. When he reaches the end of the final corridor, he will not run back to the center again.
You will be given a int[] corridors containing the lengths of all the corridors in meters. John starts in the corridor at index 0 and will run following the described strategy until he visits the ends of all the corridors at least once. Return the expected length of John's path.
|