No.1701 half price
harurun
first_vilProblem Statement
You are shopping at a store called EVEN in a shopping mall.
As the name suggests, the price of every item in the store is divisible by $2$.
The store has $N$ distinct items, and the price of each item is $a_i (1≤i≤N)$ yen.
You may halve the price of any number (possibly 0) of items, only once each.
When you choose an appropriate number of items, at least $1$, from these items, how many ways are there to choose the items so that the total price is $W$ yen?
Input
$N\ W$ $a_1 \ldots a_N$
The first line contains $N$ and $W$, separated by a space.
The second line contains $a_1 \ldots a_N$, separated by spaces.
Constraints
$1≤N≤13$
$0≤W≤10^9$
$0≤a_i≤10^9$
$a_i$ is divisible by $2$
All inputs are integers
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
3 20 40 10 20
Output
3
The condition is satisfied by
- $\displaystyle \frac{a_1}{2}=20$
- $a_2+\displaystyle \frac{a_3}{2}=20$
- $a_3=20$
so there are $3$ ways to choose the items: $\{a_1\},\{a_2,a_3\},\{a_3\}$.
Sample 2
Input
5 3 2 2 2 2 2
Output
20
We have $\frac{a_1}{2}+a_2=3$ and $a_1+\frac{a_2}{2}=3$, but note that both choose the items $\{a_1,a_2\}$, so together they count as 1 way.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。