Problem Statement
Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].
Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:
- If there are no more pancakes remaining, terminate.
- Choose a pancake uniformly at random from the pancakes that have not been chosen yet.
- If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it.
- Place the chosen pancake on top of the stack and go back to step 1.
You are given the
Definition
- Class:
- RandomPancakeStackDiv2
- Method:
- expectedDeliciousness
- Parameters:
- int[]
- Returns:
- double
- Method signature:
- double expectedDeliciousness(int[] d)
- (be sure your method is public)
Notes
- Your return value must have an absolute or relative error smaller than or equal to 1e-6
Constraints
- The number of elements in d will be between 1 and 10, inclusive.
- Each element of d will be between 1 and 100, inclusive.
Examples
{1,1,1}
Returns: 1.6666666666666667
The following scenarios may occur: With probability 1/3, Charlie chooses pancake 0 first. In this case he won't be able to add any more pancakes and the total deliciousness of his serving of pancakes will be 1. With probability 1/3, Charlie chooses pancake 1 first. What happens in the second round? With probability 1/2 he will choose pancake 0 and with probability 1/2 it will be pancake 2. In the first case the total deliciousness of Charlie's pancakes will be 2, in the second case it will be 1. With probability 1/3, Charlie chooses pancake 2 first. If he chooses pancake 0 next, the total deliciousness of his pancakes will be 2. If he happens to choose pancake 1 next (followed by pancake 0 in the third round), the total deliciousness will be 3. Summing this up, we get the expected deliciousness to be 1/3 * (1) + 1/3 * (1/2 * 1 + 1/2 * 2) + 1/3 * (1/2 * 2 + 1/2 * 3) = 5/3 = 1.666...
{10,20}
Returns: 20.0
{3,6,10,9,2}
Returns: 9.891666666666667
{10,9,8,7,6,5,4,3,2,1}
Returns: 10.999999724426809
{1,2,3,4,5,6,7,8,9,10}
Returns: 7.901100088183421
{1,1,1,1,1,1,1,1,1,1}
Returns: 1.7182818011463845
{2,7,1,8,2,8,1,8,2,8}
Returns: 7.707120535714286
{100}
Returns: 100.0
{47,40,9,1,1,4,17,8,2,53}
Returns: 34.2077094356261
{2,1,1,31,44,1,21,21,8,9}
Returns: 21.933069609788355
{3,24,31,31,10,52,52,60,46,15}
Returns: 50.1293110670194
{1,2,4,13,44,10,82,2,1,6}
Returns: 25.448012014991182
{6,71,38,1,1,11,14,1,30,1}
Returns: 34.501823467813054
{73,45,9,16,23,1,3,89,16,1}
Returns: 53.11812692901235
{29,11,1,30,24,57,1,51,11,15}
Returns: 38.55421434082893
{30,3,76,9,31,1,42,35,30,42}
Returns: 50.07904238315696
{38,3,1,1,20,91,70,1,7,36}
Returns: 43.01184551366843
{58,6,99,93,27,95,33,21,10,29}
Returns: 86.75347332451499
{60,35,5,36,90,89,40,21,35,32}
Returns: 77.06226162918873
{24,69,79,31,20,18,97,76,49,79}
Returns: 88.44129271384479
{17,82,25,72,4,86,20,67,20,44}
Returns: 75.19319444444444
{100,99,98,30,30,7,65,42,6,34}
Returns: 102.38517829585537
{73,95,42,47,56,80,94,80,96,73}
Returns: 123.55758239638446
{46,22,96,2,3,6,52,11,5,53}
Returns: 54.674823082010576
{38,2,10,2,25,37,11,2,5,4}
Returns: 26.03954420194004
{45,1,56,49,3,50,86,41,48,5}
Returns: 64.87169560185187
{24,12,1,29,2,22,16,44,31,50}
Returns: 35.01574459876544
{4,1,2,19,3,8,50,2,54,50}
Returns: 25.28321952160494
{2,22,6,5,10,92,99,65,32,58}
Returns: 54.98065917107583
{12,2,5,1,30,78,43,95,3,9}
Returns: 41.03976741622575
{27,1,39,37,89,46,11,10,21,42}
Returns: 54.700269235008804
{16,77,5,3,13,56,14,24,17,20}
Returns: 44.22237516534391
{1,4,49,83,82,12,4,4,1,1}
Returns: 44.89030974426808
{65,3,30,75,19,69,86,26,49,42}
Returns: 77.8095632164903
{13,98,10,39,77,66,14,58,94,25}
Returns: 82.24601796737213
{46,100,60,93,88,93,28,37,89,44}
Returns: 119.53908234126985
{42,77,20,84,31,97,14,33,86,79}
Returns: 94.1360827270723
{71,22,100,27,32,45,96,74,63,53}
Returns: 98.38912202380952
{37,32,81,5,1,24,1,98,89,2}
Returns: 62.37923831569666
{14,32,1,5,16,10,8,11,8,62}
Returns: 26.544673170194006
{66,11,45,39,53,18,84,94,7,5}
Returns: 74.0942297729277
{7,21,4,6,85,30,3,46,7,1}
Returns: 35.16091021825396
{1,22,4,28,16,49,2,1,18,2}
Returns: 24.695762786596116
{84,17,38,5,3,51,67,13,5,99}
Returns: 65.71564125881835
{27,25,2,41,14,80,1,3,1,12}
Returns: 38.193021660052906
{19,48,39,39,3,46,24,19,69,96}
Returns: 63.14430004409171
{1,78,1,1,66,78,1,18,33,1}
Returns: 48.96193617724868
{42,1,1,25,52,4,68,69,48,55}
Returns: 54.9373828813933
{37,76,97,8,73,36,32,58,35,84}
Returns: 92.75261298500884
{94,75,76,20,75,27,28,61,59,75}
Returns: 106.33758349867726
{29,48,74,23,71,1,99,41,66,13}
Returns: 79.49252314814814
{100,70,54,34,72,97,25,93,27,85}
Returns: 115.93858300264552
{18,50,31,89,11,24,69,73,52,5}
Returns: 71.11046957671958
{10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }
Returns: 10.999999724426809
{10, 20 }
Returns: 20.0
{3, 6, 10, 9, 2 }
Returns: 9.891666666666667
{1, 1, 1 }
Returns: 1.6666666666666667
{99, 98, 97, 96, 95, 94, 93, 92, 91, 90 }
Returns: 163.92708002645503
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Returns: 7.901100088183421
{1, 2, 4, 100, 5 }
Returns: 28.625