Codeforces
Nezzar and Lucky Number
john.k
2021. 1. 31. 23:54
반응형
Codeforces Round #698 (Div. 2)
B. Nezzar and Lucky Number
https://codeforces.com/contest/1478/problem/B
Problem - B - Codeforces
codeforces.com
문제 전문은 위 링크에서 확인하실 수 있습니다.
# 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을 더해도 맞출 수 없습니다.
반응형