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

24/63

Solve/Submission

Ranking

# 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 seyedssz Cpp14 0.05s
06 Morass Cpp14 0.05s
07 abuasifkhan Cpp14 0.35s
08 moinul_shaon Cpp14 0.35s
09 ahqmrf Cpp14 0.42s
10 underSpirit Cpp14 0.42s
11 Mahmudul_Tushar Cpp14 0.42s
12 INUA Cpp14 0.44s
13 Double_O Cpp14 0.48s
14 sahedsohel Cpp14 0.50s
15 nmunim Cpp14 0.50s
16 khatribiru Cpp14 0.53s
17 froghramar Cpp14 0.53s
18 faisal47 Cpp14 0.54s
19 smjlord068 Cpp14 0.54s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support