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 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

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