PROBLEM LINKSDIFFICULTYMEDIUM EXPLANATIONThis 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_{A}1], sum of dp[V_{A}i][V_{B}j][M_{A}] / ((S_{A}+1)*(S_{B}+1)), for 0 ≤ i ≤ S_{A}, 0 ≤ j ≤ S_{B}) is hold, where dp[V_{A}][V_{B}][M_{A}] is the answer for the input V_{A}, S_{A}, V_{B}, S_{B}, M_{A}. However there are some troubles. First, dp[V_{A}][V_{B}][M_{A}] is appeared both of the left hand side and the right hand side. So, dp[V_{A}][V_{B}][M_{A}] cannot be calculated directly by using above expression. But this is not a hard problem. Transpose that term, then we obtain dp[V_{A}][V_{B}][M_{A}] = max(dp[ceil(V_{A}/2)][ceil(V_{B}/2)][M_{A}1], sum of dp[V_{A}i] [V_{B}j] [M_{A}] / ((S_{A}+1)*(S_{B}+1)1), for 0 ≤ i ≤ S_{A}, 0 ≤ j ≤ S_{B}, i+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_{A}] ≤ X is hold. Therefore, we can calculate the correct answer by using binary search. Note that, if VA ≤ 0 and VB > 0, dp[V_{A}][V_{B}][M_{A}] = 0, and if V_{A} > 0 and V_{B} ≤ 1, dp[V_{A}][V_{B}][M_{A}] = 1. Third, if dp[a][b][c] is calculated naively with O(S_{A}*S_{B}) time, we will get TimeLimitExceeded. To avoid this, a cumulative sum can be used. Let sm[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[ai][bj][c] for 0 ≤ i ≤ S_{A}, 0 ≤ j ≤ S_{B} = sm[a][b][c]  sm[aS_{A}1][b][c]  sm[a][bS_{B}1][c] + sm[aS_{A}1][bS_{B}1][c], and sm[a][b][c] = sm[a1][b][c] + sm[a][b1][c]  sm[a1][b1][c] + dp[a][b][c]. By using this relationship, dp[a][b][c] can be calculated with O(1). SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 22 Nov '12, 16:32
