Medium Divide and Conquer > Dynamic Programming

“Why I am” is playing famous ludu game with his friends and luckily there is no snake in the game board but ladders available. Ludu board contains N + 1 grid labeled from 0 to N. “Why I am” starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When “why I am” is at grid ‘X’ and the dice number is ‘Y’ , he will move to grid ‘X+Y’ . “Why I am” finishes the game when ‘X+Y’ is equal to or greater than N. There are M ladders available in the Ludu board . The i-th ladder can help “Why I am” from X grid to Y ( Y > X ) without throwing any dice. If there is another ladder from Y , “Why I am” can take that continuously without any throw of dice. It is granted that there is no two or more ladders start from the same grid. “Why I am” need to tell the expected number of dice throwing is needed to finish the game. Can you please help him . Input: ------ The first line contains an integer T( 1<= T <= 50 ) which denotes the number of Test cases. T test cases follow . Each test case contains several lines. The first line contains two integers N(1≤N≤100000) and M(0≤M≤100).Then M lines follow, each line contains two integers Xi, Yi( 1 ≤ Xi< Yi ≤ N). Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the expected dice throwing is needed to finish the game . Output should be rounded to **3 digits after decimal point**. Constraints: ------- 1 <= T <= 50 1 <= N <= 100000 0 <= M <= 100 1 ≤ Xi < Yi ≤ N Sample Input ------------ 2 2 0 8 3 2 4 4 5 7 8 Sample Output ------------- Case 1: 1.167 Case 2: 2.344

Shakil Ahmed