Problem Statement
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
{100,23}
Returns: 1.0
The first student will certainly hit the second one, so the game will be finished after 1 turn.
{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.
{25,50,75}
Returns: 3.892383478590375
{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.
{10,10,10,12,13,13}
Returns: 41.70202803691314
{10,10,10,10,10,10}
Returns: 50.000000000000036
{100,100,100,100,100,100}
Returns: 5.0
{22,14,19,28,16}
Returns: 18.130185839277964
{84,17}
Returns: 1.337638376383764
{52,18,61,44,29,14}
Returns: 10.32032270125513
{10,20,30,40,50,60}
Returns: 12.197377738513183
{99,99,99,99,99,99}
Returns: 5.05050505050505
{99,99}
Returns: 1.0101010101010102
{91,100}
Returns: 1.0899999999999999
{83,76,42,99,15}
Returns: 4.647464861935303
{12,14,99,98}
Returns: 4.694575608442531
{24,71,13}
Returns: 4.509909595320895
{100,52,24,99}
Returns: 3.484848
{10,11,12,13,16,15}
Returns: 36.08683903099092
{50,50,50,50,50}
Returns: 8.0
{10,19,14,16,17}
Returns: 24.231064884049143
{33,34,10,82,15,17}
Returns: 11.182615665519343
{88,75,92,94,91,90}
Returns: 5.468656006585871
{14,82,35,40,50}
Returns: 7.495801603243919
{10,11}
Returns: 9.547738693467338
{98,99}
Returns: 1.0202040408081616
{24,15,19,28}
Returns: 12.864491178244636
{13, 12, 11, 17, 21, 19 }
Returns: 28.91545287387445
{93, 23, 64, 12, 59, 36 }
Returns: 7.1643961268639496
{97, 61, 98, 38, 96, 13 }
Returns: 5.201286746331806
{11, 12, 13, 14, 15, 16 }
Returns: 34.8972217863488
{10, 10, 12, 10, 11, 10 }
Returns: 46.09411684548137
{20, 60, 50, 40, 12, 15 }
Returns: 11.307301708586111
{10, 10, 12, 10, 10, 11 }
Returns: 46.105940601207884
{100, 100, 100, 42, 11 }
Returns: 4.0
{10, 10, 10, 10, 10, 10 }
Returns: 50.000000000000036
{100, 11, 100, 10 }
Returns: 3.0
{12, 18, 12, 18, 100, 57 }
Returns: 10.746387459545588
{89, 88, 86, 87, 89, 85 }
Returns: 5.640343694485206
{13, 17, 11, 13, 19, 13 }
Returns: 31.84831350197316
{100, 95, 100, 70, 99, 100 }
Returns: 5.01
{100, 90, 100, 10 }
Returns: 3.0
{10, 10, 10, 11, 10, 10 }
Returns: 48.57385173629134
{17, 29, 31, 74, 27, 11 }
Returns: 12.32726527062102
{10, 10, 10, 10, 10, 11 }
Returns: 48.606639586907626
{23, 45, 43, 77, 99, 22 }
Returns: 7.794116626561098
{10, 20, 30, 40, 50, 60 }
Returns: 12.197377738513183
{11, 22, 33, 44, 55, 66 }
Returns: 11.155585740231338
{10, 60, 50, 100, 100 }
Returns: 5.552
{19, 32, 77, 11, 11, 11 }
Returns: 13.09094716355756
{10, 15, 25, 50, 65, 75 }
Returns: 10.436360428839327
{100, 90, 100, 100, 20, 10 }
Returns: 5.0
{100, 20, 100, 10 }
Returns: 3.0
{94, 95, 96, 97, 98, 99 }
Returns: 5.154819017098075
{90, 20, 90, 10 }
Returns: 3.5070217783824535
{50, 100, 50, 100 }
Returns: 3.5