### 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 lower-numbered 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 (1-based) 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 1e-9.
-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)

 `{ 0 }` `{ 1000 }` `1`
`Returns: {1.0, 0.0 }`
 This is a meaningless round.
3)

 `{ 1, 2 }` `{ 10, 9 }` `2`
`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.501235695949892E-4, 0.7402545855229999, 0.2430210789578823, 0.0, 0.756128797472523 }```

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14284&pm=11042

lyrically

#### Testers:

SnapDragon , Rustyoldman , marek.cygan , timmac , ivan_metelsky , Egor

#### Problem categories:

Dynamic Programming