No.1701 half price
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 169
作問者 :
harurun
/ テスター :
first_vil
タグ : / 解いたユーザー数 169
作問者 :
harurun
/ テスター :
first_vil
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。