Medium Divide and Conquer > Dynamic Programming

India is going to tour Bangladesh in the next month. The two great rivals are going to face each other in Bangladesh in the month of June. They will play **2M − 1** matches in the upcoming series. All of you know the terrible event happened in the recent World Cup. So, Bangladesh will try to give real fight to the Indians. The team winning **M** matches will be the series champion. The result of each game doesn’t depend on the rest. And we are considering that there won’t be any draw/abandon in a match. What is the probability of Bangladesh to win the series? Input: ------ The first line of the input contains an integer, T, representing the number of test cases **(1 ≤ T ≤ 1000)**. For each test case, two numbers separated by space, the first one contains a number **M, 1 ≤ M ≤ 50**, representing the number of wins Bangladesh has to reach. The second one contains a number **p, 0 ≤ p ≤ 1**, representing the probability of Bangladesh to win a single match. Output: ------- For each test case the output should contain a single line with the case number and followed by the number representing the probability of Bangladesh to win the series (Print up to three decimal places). Sample Input ------------ 4 10 0.7 30 0.6 30 0.4 7 0.9 Sample Output ------------- Case 1: 0.967 Case 2: 0.940 Case 3: 0.060 Case 4: 1.000

Rezwanul Islam Maruf