DCP-126: Find The Number Back to All Problems

Medium Divide and Conquer > Dynamic Programming

Ohani is a little girl. She is very fond of numbers. But she is again very much superstitious. She thinks there are some numbers who are unlucky for her. There are some pairs (x,y) [ 0 <= x,y <= 9 ] unlucky for Ohani. A number (without leading zeros) is unlucky if it contains this pair as a substring: "xy". That means, if a number has digit y just after the digit x, then it will be unlucky for Ohani. For example: If an unlucky pair is (0,1), then number 101 is also unlucky for Ohani as 101 contains 01 as a substring. Here Ohani has a total of M unlucky pairs. Now Ohani wants to find the N-th lucky number for her between L to R. As you are a good friend of Ohani, you have to help her. Input: ------ The first line of the input will be the number of testcases Ts. The first line of each test case contains an integer M, the number of unlucky pairs for Ohani. The next M lines contains two space separated integers: x y The next line will contain three numbers, L R N. Constraints: --------- Ts <= 2000 1 <= M <= 100 0 <= x,y <= 9 1 <= L <= R <= 10^18 1 <= N <= 10^18 Output: ------- For each test case, you have to print the output in this format: "Case X: Y" Here X will be the case number. If you can't find the Nth lucky number for Ohani, Y will be a string and it will contain "No Number Found" Otherwise Y will be the lucky number you found for Ohani. Print the lucky number without any leading zeros. Sample Input ------------ 1 2 1 1 1 2 1 20 5 Sample Output ------------- Case 1: 5 Explanation of Same Testcase: ------------ Here Ohani has 2 unlucky pairs: (1,1) & (1,2). So, the unlucky numbers here between 1 to 20 are 11 & 12. As a result we found 5th lucky number is 5.

Problem Setter:

Raihat Zaman

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# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats




# User Language Timing
01 feodorv C 0.04s
02 Morass Cpp14 0.22s
03 jayanto Cpp14 0.44s
04 sahedsohel Cpp14 0.45s
05 INUA Cpp14 0.46s
06 Digonta Cpp14 0.70s
07 khatribiru Cpp14 0.71s
08 bhadra Cpp14 0.73s

Your feedback is our precious!

Or call +88 02 9853138 for support