DCP-392: Sanvi and Magical Numbers Back to All Problems

Hard Divide and Conquer > Dynamic Programming

Let us define a **Magical number** as a positive integer number which meets the following criteria on its representation: 1.) It does not contain any zeros. 2.) Each digits may appears at most twice in it. 3.) The absolute differences between summation of count of non-prime digits and count of prime-digits do not exceed K. Sanvi likes numbers which are not prime. So, **she wants to allow at most M non prime numbers to violate the rule number-2** . Sanvi also uses following algorithm in rule number-3 to calculate count of each digit **d** in a number: count( d ) = min( total occurrences of d in number, 2 ) You are given an integer number **N**. Your task is to find the total Magical numbers in the range from **1** to **N** following Sanvi's command. Since the answer could be very large, print it modulo 10^9+7. Input: ------ Input contains several test cases up to **EOF** (End Of File), which contains three space separated integers **N ( 1 ≤ N ≤ 10^18 ) , K( 0≤ K≤ 18 ) and M( 0 ≤ M ≤ 5 )** as described in the problem statement.Total test cases will not exceed **5**. Output: ------- Output a single integer denoting the total Magical numbers from **1 to N following Sanvi's command** . Since the answer could be very large print it modulo **10^9+7**. Sample Input ------------ 10 1 0 5 3 2 Sample Output ------------- 9 5 Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. So, **{2,3,5,7} are prime digits**.

Problem Setter:

Bishal Gautam

Please login to submit solution to this problem.

Problem Limits

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

Problem Stats




# User Language Timing
01 RRizkiR Cpp 0.55s
02 Morass Cpp14 0.80s
03 I_See_You Cpp 3.48s

Your feedback is our precious!

Or call +88 02 9853138 for support