問題一覧 > 通常問題

No.941 商とあまり

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : QCFiumQCFium / テスター : ynymxiaolongbaoynymxiaolongbao
2 ProblemId : 3366 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-11-30 18:08:22

問題文

黒板に一つの正整数$x$が書かれています。
いまから以下の操作を0回以上繰り返します。

  • 操作
    • 黒板に書かれている数を一つ選んで黒板から消す。消した数を$a$とする。
    ある正整数$k$を選び、$a$を$k$で割った商とあまりの2つの数を黒板に新たに書く。
うまく操作をすることで黒板に書かれる数の集合をちょうど$A$と同じにしたいです。
より正確には任意の整数$i$に対して$i$の$A$中での出現回数と黒板上の$i$の数が等しくなるようにしたいです。
$x=1,2,3,\dots,X$についてそのようなことが可能かどうかを判定してください。

入力

$N\ X$
$A_1\ A_2\ A_3\ \dots\ A_N$

$N$は$A$の要素数を表します。
$A_i$は$A$の$i$番目の要素を表します。

$1 \le N \le 100$
$1 \le X \le 5 \times 10 ^ 5$
$1 \le A_i \le X(1 \le i \le N)$
入力は全て整数

出力

長さ$X$の文字列$S$を出力してください。
$S$の前から$i$番目の文字は、$x=i$の場合に可能な場合1、そうでない場合0としてください。

サンプル

サンプル1
入力
2 5
1 1
出力
00111

例えば$x=4$の場合、最初に黒板に書かれている唯一の整数である$4$を選び、$k=3$とすると良いです。

サンプル2
入力
2 10
2 2
出力
0000000101

サンプル3
入力
1 10
5
出力
0000100000

サンプル4
入力
2 20
4 1
出力
00000000111111111111

サンプル5
入力
2 50
4 5
出力
00000000000000000000000000001000110010101001100010

サンプル6
入力
3 50
2 2 3
出力
00000000000000000000000000000000001011101011111111

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。