### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

This problem can be solved by using DP (Dynamic Programming). Basically, the relationship dp**[V_{A}][V_{B}][M_{A}]** = max(dp[ceil**(V_{A**}^{}/2)][ceil(**V _{B}**/2)][

**M**-1], sum of dp[

_{A}**V**][

_{A}-i**V**][

_{B}-j**M**] / ((

_{A}**S**+1)*(

_{A}**S**+1)), for 0 ≤

_{B}**i**≤ S

_{A}, 0 ≤

**j**≤

**S**) is hold, where dp[

_{B}**V**][

_{A}**V**][

_{B}**M**] is the answer for the input

_{A}**V**,

_{A}**S**,

_{A}**V**,

_{B}**S**,

_{B}**M**. However there are some troubles.

_{A}First, dp[**V _{A}**][

**V**]

_{B}**[M**] is appeared both of the left hand side and the right hand side. So, dp[

_{A}**V**][

_{A}**V**][

_{B}**M**] cannot be calculated directly by using above expression. But this is not a hard problem. Transpose that term, then we obtain dp[

_{A}**V**][

_{A}**V**][

_{B}**M**] = max(dp[ceil(

_{A}**V**/2)][ceil(

_{A}**V**/2)][

_{B}**M**-1], sum of dp[

_{A}**V**-i] [

_{A}**V**-j] [

_{B}**M**] / ((

_{A}**S**+1)*(

_{A}**S**+1)-1), for 0 ≤ i ≤

_{B}**S**, 0 ≤

_{A}**j**≤

**S**, i+

_{B}**j**> 0).

Second, dp[**a**][**b**][**c**] is unknown for **a** ≤ 0, **b** ≤ 0. We can use binary search for solving this issue. Let the correct answer be **P**. If we set dp[**a**][**b**][**c**] = X for **a** ≤ 0, **b** ≤ 0, then **X** ≤ dp[**V _{A}**][

**V**][

_{B}**M**] ≤

_{A}**P**or

**P**≤ dP[

**V**][

_{A}**V**][

_{B}**M**] ≤ X is hold. Therefore, we can calculate the correct answer by using binary search. Note that, if VA ≤ 0 and VB > 0, dp[

_{A}**V**][

_{A}**V**][

_{B}**M**] = 0, and if

_{A}**V**> 0 and

_{A}**V**≤ 1, dp[

_{B}**V**][

_{A}**V**][

_{B}**M**] = 1.

_{A}Third, if dp[**a**][**b**][**c**] is calculated naively with **O**(**S _{A}***

**S**) time, we will get TimeLimitExceeded. To avoid this, a cumulative sum can be used. Let sm[

_{B}**a**][

**b**][

**c**] be sum of dp[

**x**][

**y**][

**c**] for

**M**≤ x ≤

**a**,

**M**≤ y ≤

**b**, where

**M**is a small integer such as -101. Then, sum of dp[

**a-i**][

**b-j**][

**c**] for 0 ≤

**i**≤

**S**, 0 ≤

_{A}**j**≤

**S**= sm[

_{B}**a**][

**b**][

**c**] - sm[a-

**S**-1][

_{A}**b**][

**c**] - sm[

**a**][

**b**-

**S**

_{B}-1][

**c**] + sm[

**a-S**-1][

_{A}**b-S**

_{B}-1][

**c**], and sm[

**a**][

**b**][

**c**] = sm[

**a**-1][

**b**][

**c**] + sm[

**a**][

**b**-1][

**c**] - sm[

**a**-1][

**b**-1][c] + dp[

**a**][

**b**][

**c**]. By using this relationship, dp[

**a**][

**b**][c] can be calculated with O(1).

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.