Nezzar and Lucky Number (Codeforces 1478B)
Tags: Greedy, brute force

Nezzar's favorite digit among $$$1,\ldots,9$$$ is $$$d$$$. He calls a positive integer lucky if $$$d$$$ occurs at least once in its decimal representation. Given $$$q$$$ integers $$$a_1,a_2,\ldots,a_q$$$, for each $$$1 \le i \le q$$$ Nezzar would like to know if $$$a_i$$$ can be equal to a sum of several (one or more) lucky numbers.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 9$$$) — the number of test cases.The first line of each test case contains two integers $$$q$$$ and $$$d$$$ ($$$1 \le q \le 10^4$$$, $$$1 \le d \le 9$$$).The second line of each test case contains $$$q$$$ integers $$$a_1,a_2,\ldots,a_q$$$ ($$$1 \le a_i \le 10^9$$$).

Output: For each integer in each test case, print "YES" in a single line if $$$a_i$$$ can be equal to a sum of lucky numbers. Otherwise, print "NO".You can print letters in any case (upper or lower).

Note: In the first test case, $$$24 = 17 + 7$$$, $$$27$$$ itself is a lucky number, $$$25$$$ cannot be equal to a sum of lucky numbers.

Sample Inputs:
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60

Sample Outputs:
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO

Solution (Python):
def generate_result():
    t = int(input())
    ret = []
    for _ in range(t):
        (q, d) = map(int, input().split())
        if d == 2 or d == 5:
            for a in map(int, input().split()):
                if a >= d * 10 or a % d == 0:
                    yield 'YES'
                else:
                    yield 'NO'
        else:
            if d % 2 == 0:
                b = d * 10 - 1
            else:
                b = d * 10 - 10
            for a in map(int, input().split()):
                if a > b:
                    yield 'YES'
                else:
                    while a > 0:
                        if a % d == 0:
                            yield 'YES'
                            break
                        else:
                            a -= 10
                    else:
                        yield 'NO'

def main():
    print('\n'.join(generate_result()))
if __name__ == '__main__':
    main()

Solution (Python):
def generate_result():
    t = int(input())
    ret = []
    for _ in range(t):
        (q, d) = map(int, input().split())
        b = d * 10
        for a in map(int, input().split()):
            if a >= b:
                yield 'YES'
            else:
                while a > 0:
                    if a % d == 0:
                        yield 'YES'
                        break
                    else:
                        a -= 10
                else:
                    yield 'NO'

def main():
    print('\n'.join(generate_result()))
if __name__ == '__main__':
    main()

Solution (Python):
def solve(q, d, arr):
    dp = [False for i in range(101)]
    lucky = set()
    for i in range(10):
        dp[10 * i + d] = True
        dp[10 * d + i] = True
        lucky.add(10 * i + d)
        lucky.add(10 * d + i)
    for i in range(101):
        for s in lucky:
            if i - s >= 0 and dp[i - s] == True:
                dp[i] = True
                lucky.add(i)
                break
    for ai in arr:
        if ai >= 100 or dp[ai]:
            print('YES')
        else:
            print('NO')
for t in range(int(input())):
    (q, d) = map(int, input().split())
    arr = list(map(int, list(input().split())))
    solve(q, d, arr)