問題一覧 > 通常問題

No.941 Quotient and Remainder

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : QCFium / テスター : ynymxiaolongbao
お気に入りにしたユーザー ProblemId : 3366 / 自分の提出
問題文最終更新日: 2019-11-30 18:08:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

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$.
You want to perform the operations so that the set of numbers written on the blackboard becomes exactly the same as $A$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。