Codeforces Round 698 B 题解

Nezzar and Lucky Number

Nezzar's favorite digit among $1,…,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,…,a_q$, for each $1≤i≤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≤t≤9$) — the number of test cases.

The first line of each test case contains two integers $q$ and $d$ ($1≤q≤10^4$, $1≤d≤9$).

The second line of each test case contains $q$ integers $a_1,a_2,…,a_q$ ($1≤a_i≤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).

Example

input

1
2
3
4
5
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60

output

1
2
3
4
5
6
7
8
9
10
11
12
13
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO

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.

题目大意

对于数 $a$ ,如果在一个数的十进制描述法中存在任何的位等于 $d$ ,那么就称这个数是“幸运数”。现在给你 $q$ 组数和一个数 $d$ ,问你这 $q$ 组数是否能分别被表示成 $n$ 个“幸运数”的和 ($n >= 1$)。

分析

我至今没有理解我做法的正确性,但是凭感觉就想出来了然后提交居然还通过了。对于一个数 $n$ ,先去看它是不是幸运数,如果是就直接输出 YES ,如果不是的话,做 $n -= d$ 再去看 $n$ 是不是幸运数,再不是就接着减,直到不满足 $n-d > 0$ 。

这道题按照官方说明是一个dp题,我觉得我这么做会有被Hack的风险,用dp可能会更好一点。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
bool lucky(int n, int d) {
while(n >= 1) {
if(n % 10 == d) return true;
n /= 10;
}
return false;
}
int main() {
int t, q, d, n;
scanf("%d", &t);
for(int i=0; i<t; ++i) {
scanf("%d %d", &q, &d);
for(int j=0; j<q; ++j) {
scanf("%d", &n);
bool flag = false;
if(lucky(n, d)) {
printf("YES\n");
flag = true;
} else {
while(n-d > 0) {
n -= d;
if(lucky(n, d)) {
printf("YES\n");
flag = true;
break;
}
}
}
if(!flag) printf("NO\n");
}
}
return 0;
}

Codeforces Round 698 B 题解

https://mmdjiji.com/2021/01/2902/

作者

吉吉

发布于

2021-01-29

更新于

2024-03-28

许可协议