No.412 Fireworks Festival
タグ : / 解いたユーザー数 137
作問者 :
nmnmnmnmnmnmnm
Problem Statement
A-kun is going to prepare one picnic sheet each for family $B$, family $C$, and family $D$, who are going to a fireworks festival.
The minimum picnic sheet area required by each of family $B$, family $C$, and family $D$ is fixed.
Each family needs at least one picnic sheet with an area no less than the area it requires, so at least 3 sheets in total are needed for the 3 families.
A-kun has $N$ picnic sheets, whose areas are not necessarily the same.
A-kun has decided to bring some of the $N$ picnic sheets.
Note that picnic sheets cannot be joined together or anything of the sort.
How many combinations of picnic sheets to bring are there that satisfy the condition that the 3 families can use them?
Input
$B$ $C$ $D$
$N$
$E_0\ E_1\ \dots\ E_{N-1}$
$B$, $C$, $D$ are the picnic sheet areas required by the respective families.
$B$, $C$, $D$ are positive integers. $1\le B,C,D \le 100$.
$N$ is the number of picnic sheets A-kun has. $1\le N \le 30$.
$E_i$ is the area of the $i$-th picnic sheet A-kun has.
$E_i$ is a positive integer. $1\le E_i \le 100$.
Output
Output the number of combinations of picnic sheets A-kun can bring on one line.
Print a newline at the end.
Sample
Sample 1
Input
2 4 6 4 1 3 5 7
Output
2
The 3 families want picnic sheets of areas 2, 4, and 6, respectively.
A-kun has picnic sheets of areas 1, 3, 5, and 7.
To meet the families' requirements, the sheets 3, 5, and 7 are the minimum needed.
A-kun has 2 possible choices: bringing the sheets {1,3,5,7} or {3,5,7}.
Sample 2
Input
1 1 1 4 1 1 1 1
Output
5
All the families want a picnic sheet of area 1.
A-kun has 4 picnic sheets of area 1.
A-kun can choose in 4 ways to bring 3 of the 4 sheets and in 1 way to bring all 4 sheets.
Note that picnic sheets are treated as distinct even if they have the same size.
Sample 3
Input
100 100 100 1 10
Output
0
All the families want a picnic sheet of area 100.
However, A-kun has only 1 picnic sheet, of area 10.
There is no way of bringing sheets that meets the families' requirements, so the answer is 0.
Sample 4
Input
15 25 35 10 10 20 30 40 50 60 70 80 90 100
Output
932
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。