No.941 Quotient and Remainder
タグ : / 解いたユーザー数 12
作問者 :
QCFium
/ テスター :
ynymxiaolongbao
Problem Statement
A single positive integer $x$ is written on a blackboard.
You will now repeat the following operation 0 or more times.
- Operation Choose one number written on the blackboard and erase it from the blackboard. Let $a$ be the erased number.
Choose a positive integer $k$, and newly write two numbers on the blackboard: the quotient and the remainder of dividing $a$ by $k$.
More precisely, you want the number of occurrences of $i$ in $A$ to be equal to the number of $i$ on the blackboard for every integer $i$.
For each of $x=1,2,3,\dots,X$, determine whether this is possible.
Input
$N\ X$ $A_1\ A_2\ A_3\ \dots\ A_N$
$N$ represents the number of elements of $A$.
$A_i$ represents the $i$-th element of $A$.
$1 \le N \le 100$
$1 \le X \le 5 \times 10 ^ 5$
$1 \le A_i \le X(1 \le i \le N)$
All inputs are integers.
Output
Output a string $S$ of length $X$.
The $i$-th character from the front of $S$ should be 1 if it is possible for $x=i$, and 0 otherwise.
Sample
Sample 1
Input
2 5 1 1
Output
00111
For example, when $x=4$, you can choose $4$, the only integer initially written on the blackboard, and let $k=3$.
Sample 2
Input
2 10 2 2
Output
0000000101
Sample 3
Input
1 10 5
Output
0000100000
Sample 4
Input
2 20 4 1
Output
00000000111111111111
Sample 5
Input
2 50 4 5
Output
00000000000000000000000000001000110010101001100010
Sample 6
Input
3 50 2 2 3
Output
00000000000000000000000000000000001011101011111111
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。