問題一覧 > 通常問題

No.1701 half price

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 172
作問者 : harurunharurun / テスター : first_vilfirst_vil
1 ProblemId : 5971 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-14 13:08:27

問題文

あなたはショッピングモールにあるEVENという店で買い物をします。

名前の通り、その店のすべての商品の値段は $2$ で割り切れます。

その店には $N$ 個の異なる商品があり、各商品の値段は $a_i (1≤i≤N)$ 円です。

あなたは好きな数(0でもよい)の商品の値段を一度だけ半額にできます。

これらの商品から $1$ つ以上の適当な数の商品を選んだ時、値段の合計が $W$ 円になる商品の選び方は何通りあるでしょうか。

入力

$N\ W$
$a_1 \ldots a_N$

  • 1行目に、 $N$ と $W$ が空白区切りで与えられる。

  • 2行目に、 $a_1 \ldots a_N$ が空白区切りで与えられる。

制約

  • $1≤N≤13$

  • $0≤W≤10^9$

  • $0≤a_i≤10^9$

  • $a_i$ は $2$ で割り切れる

  • 入力は全て整数である

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 20
40 10 20
出力
3

条件を満たすのは、

  • $\displaystyle \frac{a_1}{2}=20$
  • $a_2+\displaystyle \frac{a_3}{2}=20$
  • $a_3=20$

より、商品の選び方は $\{a_1\},\{a_2,a_3\},\{a_3\}$ の $3$ 通りです。

サンプル2
入力
5 3
2 2 2 2 2
出力
20

$\frac{a_1}{2}+a_2=3$ , $a_1+\frac{a_2}{2}=3$ ですが、商品の選び方はどちらも $\{a_1,a_2\}$ なので合わせて 1通りであることに注意してください。

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