問題一覧 > 通常問題

No.1538 引きこもりさんは引き算が得意。

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 36
作問者 : とりゐとりゐ / テスター : 57tggx57tggx logxlogx 遭難者遭難者 Re_menal2Re_menal2 ゅゅゅゅ pepper_aobutapepper_aobuta
11 ProblemId : 6529 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-06 17:45:49

問題文

黒板に $N$ 個の整数 $A_1,A_2,\ldots, A_N$ が書かれています．引き算が得意なゅゅちゃんは $0$ 以上 $N-1$ 以下の任意の回数，以下の操作を繰り返すことができます．

  • 黒板に書かれている数を $2$ つ選んで消す．消した数を $x,y$ として，$x-y$ と $y-x$ のどちらか一方を黒板に書く．
この操作によって，黒板に書かれている数に $K$ が含まれている状態にすることができるか判定してください．

入力

$N\ K$
$A_1\ A_2\ \ldots\ A_N$

  • 入力は全て整数である．
  • $2\leq N\leq 20$
  • $-10^9\leq K\leq 10^9$
  • $-10^9\leq A_i\leq10^9\ (1\leq i\leq N)$

出力

$K$ が含まれている状態にすることが可能ならば Yes を，そうでないならば No を出力してください．

サンプル

サンプル1
入力
4 6
7 -2 5 3
出力
Yes

以下の操作によって，$6$ を黒板に残すことができます．

  1. まず $7$ と $3$ を選んで消し，$7-3$ を書く．このとき，黒板には $-2,5,4$ が書かれている．
  2. 次に $4$ と $-2$ を選んで消し，$4-(-2)$ を書く．このとき，黒板には $5,6$ が書かれている．

サンプル2
入力
4 10
1 3 5 7
出力
Yes

以下の操作によって，$10$ を黒板に残すことができます．

  1. まず $3$ と $1$ を選んで消し，$3-1$ を書く．このとき，黒板には $5,7,2$ が書かれている．
  2. 次に $2$ と $5$ を選んで消し，$2-5$ を書く．このとき，黒板には $7,-3$ が書かれている．
  3. 最後に $7$ と $-3$ を選んで消し，$7-(-3)$ を書く．このとき，黒板には $10$ が書かれている．

サンプル3
入力
3 6
4 -12 16
出力
No

どのように操作を行っても，$6$ を黒板に残すことはできません．

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