問題一覧 > 通常問題

No.412 花火大会

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 99
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
4 ProblemId : 770 / 出題時の順位表
問題文最終更新日: 2016-08-12 22:34:33

問題文

A君は花火大会に行く家族$B$、家族$C$、家族$D$のためにレジャーシートを1枚ずつ用意することになりました。
家族$B$、家族$C$、家族$D$が必要とする最低限必要なレジャーシートの面積がそれぞれ決まっています。
各家族の必要とする面積以上のレジャーシートがそれぞれ最低1枚、3家族で合計3枚は必要です。

A君は$N$枚のレジャーシートを持っておりそれぞれの面積は同じとは限りません。
A君は$N$枚のうちからレジャーシートをいくつか持って行くことにしました。
なお、レジャーシートはくっつけるなどの事はできません。

3つの家族が使用できる条件を含むレジャーシートの持っていきかたの組み合わせはいくつか?

入力

$B$ $C$ $D$
$N$
$E_0\ E_1\ \dots\ E_{N-1}$

$B$、$C$、$D$はそれぞれ家族が必要とするレジャーシートの面積。
$B$、$C$、$D$は正の整数。$1\le B,C,D \le 100$。
$N$はA君が持っているレジャーシートの数。$1\le N \le 30$。
$E_i$はA君が持っている$i$番目のレジャーシートの面積。
$E_i$は正の整数。$1\le E_i \le 100$。

出力

A君が持っていくレジャーシートの組み合わせの数を1行で出力せよ。
最後に改行してください。

サンプル

サンプル1
入力
2 4 6
4
1 3 5 7
出力
2

3つの家族はそれぞれ面積2、4、6のレジャーシートを欲しています。
A君は面積1、3、5、7のレジャーシートを持っています。
家族の要求を満たすためには3、5、7のレジャーシートが最低限必要です。
A君は{1,3,5,7}か{3,5,7}のレジャーシートを持っていく2通りの選択ができます。

サンプル2
入力
1 1 1
4
1 1 1 1
出力
5

すべての家族が面積1のレジャーシートを欲しています。
A君は面積1のレジャーシートを4枚持っています。
A君は4枚のうち3枚を持っていく4通りと4枚とも持っていく1通りの選択ができます。
同じサイズでもレジャーシートは違うものとして扱うので注意してください。

サンプル3
入力
100 100 100
1
10
出力
0

すべての家族が面積100のレジャーシートを欲しています。
しかし、A君は面積10のレジャーシートを1枚しか持っていません。
家族の要求を満たすような持って行きかたは無いので0通りです。

サンプル4
入力
15 25 35
10
10 20 30 40 50 60 70 80 90 100
出力
932

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