Nezzar and Lucky Number

Codeforces Round #698 (Div. 2)

B. Nezzar and Lucky Number

https://codeforces.com/contest/1478/problem/B

Problem - B - Codeforces

문제 전문은 위 링크에서 확인하실 수 있습니다.

 

# https://codeforces.com/contest/1478/problem/B

def lucky(n, d):
    if str(d) in str(n):
        return True
    else:
        return False

n = int(input())
for _ in range(n):
    q,d = [int(i) for i in input().split()]
    arr = [int(i) for i in input().split()]
    if d == 1:
        for _ in range(len(arr)):
            print("YES")
        continue
    for i in arr:
        while i > 0:
            if lucky(i, d):
                print("YES")
                break
            else:
                i = i - d
        else:
            print("NO")

유튜브의 강의를 참고하였습니다.

https://www.youtube.com/watch?v=DFsfAeFocKM

일단 d = 1일때는

1을 연속해서 더해서 모든 값을 나타낼 수 있기 때문에

모든 값에 YES가 나옵니다.

 

이외의 경우에는

10d 보다 큰 수가 나올 경우 lucky number의 합으로 만들 수 있어서

YES가 나옵니다.

 

예를 들면 d=7 일때

80,81...

73+7 74+7...

 

90,91...

73+17 74+17...

 

100,101...

73+27 74+27...

 

1000, 1001...

703+297, 704+297...

 

10d보다 작은 수의 경우 d를 빼가면서 검증해봅니다.

마찬가지로 d=7일때

69

62+7

55+7+7

48+7+7+7

41+7+7+7+7

34+7+7+7+7+7

27+7+7+7+7+7+7

 

25

18+7

11+7+7

6+7+7+7

 

d~9d의 합으로 나타낼 수 없다면

17 27 37 47 57 67로도 나타낼 수 없습니다.

1의 자리 수가 안맞기 때문에 10 20 30을 더해도 맞출 수 없습니다.