#CF550B. 奥赛出题

奥赛出题

CF550B Preparing Olympiad

题目描述

\hspace{15pt}你有 nn 道题目,第 ii 道题目的难度为整数 cic_i。现在你要从中选取一些题目组成一个题集,题集必须满足:

∙ \hspace{23pt}\bullet\,至少包含 22 道题目;

∙ \hspace{23pt}\bullet\,题集的总难度(所选题目难度之和)不小于 ll,且不大于 rr;

∙ \hspace{23pt}\bullet\,所选题目中最难题与最易题的难度之差至少为 xx。

\hspace{15pt}请你计算一共有多少种不同的题集。只要选取的题目集合不同,就视为不同的题集。

输入格式

\hspace{15pt}第一行输入四个整数 $n, l, r, x \left(1 \leqq n \leqq 15;\ 1 \leqq l \leqq r \leqq 10^9;\ 1 \leqq x \leqq 10^6\right)$,分别代表题目数量、总难度下限、总难度上限与难度差下限。

\hspace{15pt}第二行输入 nn 个整数 $c_1, c_2, \dots, c_n \left(1 \leqq c_i \leqq 10^6\right)$ 代表每道题目的难度。

输出格式

\hspace{15pt}输出一行一个整数,代表符合条件的题集数量。

测试样例

3 5 6 1
1 2 3
2

样例 1 解释

\hspace{15pt}三道题目的难度分别为 1,2,31,2,3。至少选两道的选法共有 44 种:

∙ \hspace{23pt}\bullet\,选第 1,21,2 题:总难度 33,不在 [5,6][5,6] 内,不合法;

∙ \hspace{23pt}\bullet\,选第 1,31,3 题:总难度 44,不在 [5,6][5,6] 内,不合法;

∙ \hspace{23pt}\bullet\,选第 2,32,3 题:总难度 55,难度差 ∣3−2∣=1≧1|3-2| = 1 \geqq 1,合法;

∙ \hspace{23pt}\bullet\,选第 1,2,31,2,3 题:总难度 66,难度差 ∣3−1∣=2≧1|3-1| = 2 \geqq 1,合法。

\hspace{15pt}因此答案为 22。

4 40 50 10
10 20 30 25
2

样例 2 解释

\hspace{15pt}只有两种合法题集:{10,30}\{10,30\}(总难度 4040,难度差 2020)与 {20,30}\{20,30\}(总难度 5050,难度差 1010)。

5 25 35 10
10 10 20 10 20
6

样例 3 解释

\hspace{15pt}难度为 1010 的题目有 33 道,难度为 2020 的题目有 22 道。任取一道难度 1010 和一道难度 2020,总难度都是 3030,难度差都是 1010,都满足条件,共有 3×2=63 \times 2 = 6 种。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦n≦151 \leqq n \leqq 15,1≦l≦r≦1091 \leqq l \leqq r \leqq 10^9,1≦x≦1061 \leqq x \leqq 10^6,1≦ci≦1061 \leqq c_i \leqq 10^6。

\hspace{15pt}题集的总数不超过 215=3.2768×1042^{15} = 3.2768 \times 10^4,直接枚举每一种选法即可。

\hspace{15pt}由于每道题目的难度都不超过 10610^6,题集的总难度不超过 1.5×1071.5 \times 10^7,因此当 ll 超过这个值时答案为 00。