Algorithm

Problem link- https://www.spoj.com/problems/WORMS/

WORMS - Play with Digit Seven

#big-numbers #dynamic-programming #digit-dp-1

 

Description

A natural number x is called a good number if one or two of the next two conditions is satisfied:

  • 7 is a divisor of x.
  • 7 is a digit of x.

Task

Write a program that:

  • reads a number n from the standard input,
  • computes the number of good numbers in range [1, 10n],
  • writes the result to the standard output.

Solve the problem by at most 0.5kB of source code.

Input

The input begins with an integer t (t <= 210), the number of test cases.t test cases follow.

For each test case, the first and only line contains an integer n (1 <= n <= 500).

Output

For each test case the output consists of one line that contains the answer.

Example

Sample input:
3
1
2
1

Sample output:
1
30
1

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

dp = [[0 for i in range(7)] for j in range(505)]
dp[0][0] = 1
for i in range(0, 500):
    for j in range(0, 7):
        for k in range(0, 10):
            if k != 7:
                dp[i + 1][(10 * j + k) % 7] += dp[i][j]
t = int(input())
for i in range(0, t):
    n = int(input())
    sum = 0
    for j in range(1, 7):
        sum += dp[n][j]
    print(10 ** n - sum - 1)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
1
2
1

Output

x
–
+
cmd
1
30
1
Advertisements

Demonstration

SPOJ Solution-Play with Digit Seven-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python