Problem Statement 
 You have advanced to Online Round 5 of the 2010 CodeTopper Open!
There are N people competing in this round
and the k highest scoring competitors will advance to the Onsite Semifinal Rounds.
The competitors are numbered from 0 to N  1.
In Online Round 5, competitor i will score an integer point value between worst[i] and best[i], inclusive.
Every integer point value in this range has the same probability.
If two or more competitors get the same score, the lowernumbered competitors are preferred when determining the top k.
After the k advancers are determined, they will be assigned to either Semifinal 1 or Semifinal 2.
In order of increasing competitor number, the advancers are assigned to the Semifinal rounds in the following order:
1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, ...
Note that the scores of the advancers are not considered when determining the Semifinal assignment.
Return a double[] containing 2N elements
where the (2i+j)th (1based) element is the probability that competitor i is assigned to Semifinal j.


Definition 
 Class:  SemifinalAssignment  Method:  getProbability  Parameters:  int[], int[], int  Returns:  double[]  Method signature:  double[] getProbability(int[] worst, int[] best, int k)  (be sure your method is public) 




Notes 
  Each element of the returned value must have an absolute or relative error less than 1e9. 
  You can assume that scores of the competitors are mutually independent uniform random variables. 

Constraints 
  worst will contain between 1 and 25 elements, inclusive. 
  worst and best will contain the same number of elements. 
  Each element of worst and best will be between 0 and 1,000, inclusive. 
  For each index i, worst[i] will be less than or equal to best[i]. 
  k will be between 1 and the number of elements in worst, inclusive. 

Examples 
0)  
 { 1, 0, 1, 1, 1, 1 }  { 1, 3, 1, 1, 1, 1 }  4 
 Returns: {1.0, 0.0, 0.0, 0.75, 0.0, 1.0, 0.75, 0.25, 0.25, 0.0, 0.0, 0.0 }  There are two possible outcomes of this round:
 Competitor 1 scores positive points with 75% probability. Then the advancers are competitors 0, 1, 2 and 3.
Competitors 0 and 3 are assigned to Semifinal 1, and competitors 1 and 2 are assigned to Semifinal 2.
 Competitor 1 scores zero points with 25% probability. Then the advancers are competitors 0, 2, 3 and 4.
Competitors 0 and 4 are assigned to Semifinal 1, and competitors 2 and 3 are assigned to Semifinal 2.



1)  
 { 11, 11, 11, 10 }  { 12, 12, 12, 11 }  2 
 Returns: {0.875, 0.0, 0.125, 0.625, 0.0, 0.375, 0.0, 0.0 }  Competitor 0 will fail to advance only when he/she scores 11 points and each of competitors 1 and 2 scores 12 points. 


2)  
  Returns: {1.0, 0.0 }  This is a meaningless round.



3)  
  Returns: {1.0, 0.0, 0.0, 1.0 }  This is also meaningless because the assignment is based on competitor numbers, not on their scores.



4)  
 { 1, 1, 1, 2, 2, 2, 3, 3, 3 }  { 4, 5, 6, 4, 5, 6, 4, 5, 6 }  1 
 Returns:
{0.02041666666666667, 0.0, 0.11527777777777776, 0.0, 0.25810185185185186, 0.0, 0.011435185185185187, 0.0, 0.0875925925925926, 0.0, 0.23171296296296295, 0.0, 0.005046296296296296, 0.0, 0.0625, 0.0, 0.2079166666666667, 0.0 }  

5)  
 { 1, 2, 5, 4 }  { 9, 7, 8, 9 }  3 
 Returns:
{0.6527777777777779, 0.0, 0.34722222222222227, 0.21296296296296297, 0.0, 0.9305555555555559, 0.0, 0.856481481481482 }  

6)  
 { 3, 317, 25, 447, 96, 333, 361, 103 }  { 947, 773, 601, 544, 594, 399, 786, 954 }  6 
 Returns:
{0.6649201903354007, 0.0, 0.32850646461892563, 0.6163949837246063, 0.006573345045673984, 0.4544927900216218, 0.2180181176461977, 0.7769069045939901, 0.3815407626549669, 0.15220532165978432, 0.6601865341758356, 8.501235695949892E4, 0.7402545855229999, 0.2430210789578823, 0.0, 0.756128797472523 }  
