The Millionaire and the Orphans
Time limit1sMemory limit1024 MB
Given three orphanages with fixed basket areas and children counts, compute the expected total gift value each orphanage catches as gifts are thrown in order.
- Level
Medium5 of 10
- Topics
- Probability, Math, Dynamic programming
- Solved
- No attempts yet
Problem
In Dickensian England there lived a millionaire named Mortimer. In the same town stood three orphanages, home to orphans whom Mortimer liked to give Christmas presents.
The gifts were handed out as follows:
- Every orphan takes a basket from their own orphanage and uses it to catch gifts.
- Mortimer throws the gifts one at a time toward the children, who catch them with their baskets.
- Every gift is always caught by exactly one child.
- Which child catches a gift is random: the probability that a particular child catches the current gift is proportional to the area of that child's basket mouth.
- All children from the same orphanage have baskets of the same area.
- As soon as a child catches a gift, they return to their orphanage with it and take no further part in catching.
- There may be more children than gifts.
Each gift has a value. For each orphanage, determine the expected total value of the gifts caught by that orphanage's children.
Input
- Line 1: two integers and (, ) — the number of children in the first orphanage and the area of their baskets.
- Line 2: two integers and (, ) — the same for the second orphanage.
- Line 3: two integers and (, ) — the same for the third orphanage.
- Line 4: an integer () — the number of gifts.
- Each of the next lines contains one integer in the range — the value of a gift. Mortimer throws the gifts in exactly this order.
Output
Print three lines. On the -th line, print the expected total value of the gifts caught by the children of the -th orphanage, rounded to exactly six digits after the decimal point (round half up), always shown with six decimal places.