This page is still under construction.

Parts of this page are still being built. What you see may change.

The Millionaire and the Orphans

Time limit1sMemory limit1024 MB

Summary
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:

  1. Every orphan takes a basket from their own orphanage and uses it to catch gifts.
  2. Mortimer throws the gifts one at a time toward the children, who catch them with their baskets.
  3. Every gift is always caught by exactly one child.
  4. 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.
  5. All children from the same orphanage have baskets of the same area.
  6. As soon as a child catches a gift, they return to their orphanage with it and take no further part in catching.
  7. 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 L1L_1 and K1K_1 (0≤L1≤1000 \le L_1 \le 100, 1≤K1≤1001 \le K_1 \le 100) — the number of children in the first orphanage and the area of their baskets.
  • Line 2: two integers L2L_2 and K2K_2 (0≤L2≤1000 \le L_2 \le 100, 1≤K2≤1001 \le K_2 \le 100) — the same for the second orphanage.
  • Line 3: two integers L3L_3 and K3K_3 (0≤L3≤1000 \le L_3 \le 100, 1≤K3≤1001 \le K_3 \le 100) — the same for the third orphanage.
  • Line 4: an integer NN (1≤N≤L1+L2+L31 \le N \le L_1 + L_2 + L_3) — the number of gifts.
  • Each of the next NN lines contains one integer in the range 1…10001 \ldots 1000 — the value of a gift. Mortimer throws the gifts in exactly this order.

Output

Print three lines. On the ii-th line, print the expected total value of the gifts caught by the children of the ii-th orphanage, rounded to exactly six digits after the decimal point (round half up), always shown with six decimal places.

Examples3

  1. Example 1

    Input
    1 1
    1 2
    1 3
    2
    10
    20
    
    Expected output
    6.666667
    11.333333
    12.000000
    
  2. Example 2

    Input
    2 1
    0 5
    1 3
    1
    100
    
    Expected output
    40.000000
    0.000000
    60.000000
    
  3. Example 3

    Input
    2 5
    2 5
    2 5
    3
    6
    6
    6
    
    Expected output
    6.000000
    6.000000
    6.000000