TopCoder problem "SchoolTrip" used in SRM 384 (Division I Level Two)



Problem Statement

    There are n students standing in a circle and playing a game with a ball. The students are numbered from 0 to n-1 in clockwise order. On each turn, a student must take the ball and throw it at another student in the circle. Student i has a probability[i] percent chance of hitting the target student, and if he is successful, the student who is hit must leave the circle. Turns go in clockwise order, and student 0 gets the first turn. They are not allowed to skip turns. The game ends when there is only one student left in the circle.



The students are playing this game against their will, so their common goal is to finish the game in the least number of turns. Return the expected number of turns the game will last.
 

Definition

    
Class:SchoolTrip
Method:duration
Parameters:int[]
Returns:double
Method signature:double duration(int[] probability)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
-Each student does not worry about how long he will stay in the circle, only the total game time matters.
 

Constraints

-probability will contain between 2 and 6 elements, inclusive.
-Each element of probability will be between 10 and 100, inclusive.
 

Examples

0)
    
{100,23}
Returns: 1.0
The first student will certainly hit the second one, so the game will be finished after 1 turn.
1)
    
{50,50}
Returns: 2.0
With probability 1/2 the game will be finished after 1 turn, with probability 1/4 after 2 turns, .. with probability 1/2^k after k turns. The infinite sum 1*1/2 + 2*1/4 + 3*1/8 +.. n*1/2^n = 2.
2)
    
{25,50,75}
Returns: 3.892383478590375
3)
    
{100,100,100,42,11}
Returns: 4.0
The first two students will start out by hitting the last two students. After that, there will be three students remaining, and all of them always hit their targets, so only two more turns will be required for the game to end.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7657

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10808&pm=7657

Writer:

rasto6sk

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Dynamic Programming, Math, Recursion