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.