問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : とりゐとりゐ / テスター : 57tggx57tggx logxlogx 遭難者遭難者 Re_menal2Re_menal2 ゅゅゅゅ pepper_aobutapepper_aobuta
8 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もしくは右上の雲マークをクリックしてアカウントを作成してください。