#P4773. Expected Contest Penalty Calculation

    ID: 18017 Type: Default 1000ms 256MiB

Expected Contest Penalty Calculation

Expected Contest Penalty Calculation

JerryC, a devoted coder, uses a mystical method at 23:05 to forecast the outcome of his submissions using the fishes in his aquarium. In his tank there are red carps and green carps (and no donkeys!). When his prophecy indicates a red carp, his submission will result in a Wrong Answer (WA) and he suffers a penalty of 5 minutes in addition to the submission time. When the prophecy shows a green carp, his submission is Accepted (AC).

The contest mechanics are as follows:

  • The first submission is made at 5 minutes and every subsequent submission is made after a 5‐minute cooldown.
  • JerryC works on problems sequentially. He keeps trying the same problem until he gets AC. For each problem solved, the penalty time is computed as the time (in minutes) at which the AC submission is made plus an extra 5 minutes for every WA submission for that problem.
  • Before each submission (while there is at least one fish in the tank) JerryC uses his prophecy: he randomly picks one fish from the tank. If the fish is red, his submission is WA; if it is green, the submission is AC. In either case, the fish is removed from the tank.
  • After all the fish have been used, JerryC makes one final submission without using his prophecy and it is guaranteed to be AC. (This final submission does not add any extra WA‐penalty but its submission time is counted.)

Thus, if a problem is solved using prophecy the following holds. Suppose that in a particular problem the prophecy is used a total of m times (i.e. m submissions are made) with the first m-1 submissions coming out as WA (red carp) and the mth submission is AC (green carp). If the submission times (in minutes) are 5, 10, 15, … then the penalty time for that problem is:

Penalty=5m+5(m1)=5(2m1).\text{Penalty} = 5m + 5(m-1) = 5(2m-1).

The submissions are carried out one after the other. All the prophecy-based submissions (which total to R+G, where R is the number of red carps and G is the number of green carps in the tank) occur in some random order. They naturally partition into blocks; each block corresponds to one problem that is eventually solved. In a block the number of submissions equals the position of the green carp drawn in that block. After using all R+G fish, a final submission is made; if the total number of prophecy submissions is S = R+G, then the time for the final AC is \(5(S+1)\) minutes.

Overall, the total contest penalty is the sum over all problems solved (each with its own AC time plus 5 minutes per preceding WA in that problem) plus the penalty from the final submission. Since the order of the fish drawn is uniformly random, you are asked to compute the expected total penalty time.

Input format note: If there are no green carps (i.e. G = 0) then JerryC never gets an AC using prophecy; in that case, he would make R WA submissions for the one problem and then the final guaranteed AC. That problem’s penalty is computed as \(5(\text{final submission index}) + 5 \times (\text{number of WA submissions})\), which simplifies to \(5(2R+1)\) minutes.

Mathematical formulation (for G \(> 0\)):
Let the total number of fish be \(R+G\) and denote by \(g_1, g_2, \dots, g_G\) the positions (in the sequence of prophecy submissions) where a green carp is drawn (i.e. the order statistics in a random permutation of the fish). Then the penalty for the block ending at \(g_i\) is

[ 5\Bigl(g_i + (g_i-g_{i-1}-1)\Bigr) = 5(2g_i - g_{i-1} - 1),]

with (g_0 = 0). Summing over all blocks and adding the penalty for the final submission at time (5(R+G+1)), the total penalty is

[ 5\Bigl(\sum_{i=1}^{G}g_i + g_G + R+1\Bigr). ]

Because the positions (g_i) are random with (E[g_i] = \frac{i(R+G+1)}{G+1}), the expected total penalty (for (G>0)) is

[ \text{Expected Penalty} = 5\Biggl( \frac{R+G+1}{G+1}\cdot\frac{G(G+1)}{2} + \frac{G(R+G+1)}{G+1} + R+1 \Biggr) = 5\Biggl( \frac{G(R+G+1)(G+3)}{2(G+1)} + R+1 \Biggr). ]

Given integers R and G, compute and print the expected total penalty time.

inputFormat

The input consists of a single line containing two non‐negative integers R and G separated by spaces — the number of red and green carps, respectively. (\(0 \le R, G \le 10^6\))

outputFormat

Print the expected total penalty time in minutes. For cases where the answer is not an integer, output a floating point number. An answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

0 1
15.000000