Algorithm
Problem link- https://www.spoj.com/problems/WORMS/
WORMS - Play with Digit Seven
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
1
2
1
Output
30
1
Demonstration
SPOJ Solution-Play with Digit Seven-Solution in C, C++, Java, Python