DCP-104: Why I am and Ludu Back to All Problems

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

Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 1.00
Go 1.00
Java 1.00
JavaScript 1.00
Objective-C 1.00
Perl 1.00
PHP 1.00
Python 1.00
Python3 1.00
Ruby 1.00
VB.Net 1.00

Problem Stats




# User Language Timing
01 feodorv C 0.01s
02 tariqiitju Cpp14 0.03s
03 njrafi Cpp14 0.04s
04 sakib_muhit Cpp14 0.04s
05 Morass Cpp14 0.05s
06 seyedssz Cpp14 0.05s
07 moinul_shaon Cpp14 0.35s
08 abuasifkhan Cpp14 0.35s
09 underSpirit Cpp14 0.42s
10 ahqmrf Cpp14 0.42s
11 Mahmudul_Tushar Cpp14 0.42s
12 INUA Cpp14 0.44s
13 Double_O Cpp14 0.48s
14 nmunim Cpp14 0.50s
15 sahedsohel Cpp14 0.50s
16 froghramar Cpp14 0.53s
17 khatribiru Cpp14 0.53s
18 smjlord068 Cpp14 0.54s
19 faisal47 Cpp14 0.54s

Your feedback is our precious!

Or call +88 02 9853138 for support