시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 2048 MB222100.000%

문제

Alice and Bob engage in a strategic duel called Number Magic, where Alice initially chooses a positive integer $N$ called the starting number. The game permits two specific magic operations to be performed on a positive integer $K$:

  1. Say $K$ has $D$ digits. One operation is to add the number consisting of $D$ $1$-digits (i.e. $\sum_{j=0}^{D-1}{10^j}$) to $K$. For example, if $K=93091$ then this magic operation would add $11111$ to $K$ resulting in $104202$; if $K=99$ then it becomes $110$; if $K=9$ it becomes $10$.
  2. If $K>1$, one operation is to divide $K$ by $2$ and round down. For example, if $K=2$ then it becomes $1$, if $K=13$ it becomes $6$.

There are $Q$ rounds of the duel. In round $i$, Bob picks a target number $M_i$ and the Alice must determine if it is possible to apply at most $32$ magic operations to the starting number $N$ in order to reach $M_i$. That is, Alice should find a sequence $N_0,N_1,N_2,\dots ,N_k$ with $k≤32$ such that $N_0=N$ and $N_i$ can be obtained by applying a magic operation to $N_{i-1}$ for each $1≤i≤k$? Note, only $M_i$ will change between rounds: $N$ will be the same in each round.

This is a very challenging game, Alice has asked you for help!

입력

The first line of input contains two space integers, $N$ ($1≤N≤10^{16}$) and $Q$ ($1≤Q≤1000$) where $N$ is the starting number that Alice chooses and $Q$ is the number of rounds.

Then $Q$ lines follow, the $i$’th such line containing a single integer $M_i$ ($1≤M_i≤10^{16}$) indicating the target number that Bob chooses for round $i$.

출력

Output $Q$ lines where line $i$ contains the text YES if it is possible to transform $N$ into $M_i$ using at most $32$ applications of magic, otherwise line $i$ contains the text NO.

예제 입력 1

7 2
43
28

예제 출력 1

YES
YES

예제 입력 2

74 1
18

예제 출력 2

YES

예제 입력 3

22 2
9961
1

예제 출력 3

NO
YES

출처

University > University of Alberta Programming Contest > UAPC 2024 > Division 1 D번

  • 문제를 만든 사람: Answer, Maple