CF550B Preparing Olympiad
题目描述
你有 n 道题目,第 i 道题目的难度为整数 ci。现在你要从中选取一些题目组成一个题集,题集必须满足:
∙至少包含 2 道题目;
∙题集的总难度(所选题目难度之和)不小于 l,且不大于 r;
∙所选题目中最难题与最易题的难度之差至少为 x。
请你计算一共有多少种不同的题集。只要选取的题目集合不同,就视为不同的题集。
输入格式
第一行输入四个整数 $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)$,分别代表题目数量、总难度下限、总难度上限与难度差下限。
第二行输入 n 个整数 $c_1, c_2, \dots, c_n \left(1 \leqq c_i \leqq 10^6\right)$ 代表每道题目的难度。
输出格式
输出一行一个整数,代表符合条件的题集数量。
测试样例
3 5 6 1
1 2 3
2
样例 1 解释
三道题目的难度分别为 1,2,3。至少选两道的选法共有 4 种:
∙选第 1,2 题:总难度 3,不在 [5,6] 内,不合法;
∙选第 1,3 题:总难度 4,不在 [5,6] 内,不合法;
∙选第 2,3 题:总难度 5,难度差 ∣3−2∣=1≧1,合法;
∙选第 1,2,3 题:总难度 6,难度差 ∣3−1∣=2≧1,合法。
因此答案为 2。
4 40 50 10
10 20 30 25
2
样例 2 解释
只有两种合法题集:{10,30}(总难度 40,难度差 20)与 {20,30}(总难度 50,难度差 10)。
5 25 35 10
10 10 20 10 20
6
样例 3 解释
难度为 10 的题目有 3 道,难度为 20 的题目有 2 道。任取一道难度 10 和一道难度 20,总难度都是 30,难度差都是 10,都满足条件,共有 3×2=6 种。
提示
对于 100% 的数据,1≦n≦15,1≦l≦r≦109,1≦x≦106,1≦ci≦106。
题集的总数不超过 215=3.2768×104,直接枚举每一种选法即可。
由于每道题目的难度都不超过 106,题集的总难度不超过 1.5×107,因此当 l 超过这个值时答案为 0。