A6276. 组题目
编程题
普及/提高-
知识点
题目描述
你有 $n$ 道题目，第 $i$ 道题目的难度为整数 $c_i$。
现在你想从中选出一些题目，用来组成一次比赛的题集。
这个题集要满足以下条件：
1. **至少两道题目**；
2. **总难度**（所选题目难度之和）在区间 $[l, r]$ 内：
- 总难度 $\ge l$；
- 总难度 $\le r$；
3. 所选题目中，**最难题的难度**与**最易题的难度**之差 **至少为 $x$**。
问：一共有多少种不同的**题集选择方法**满足上述所有条件？
现在你想从中选出一些题目，用来组成一次比赛的题集。
这个题集要满足以下条件：
1. **至少两道题目**；
2. **总难度**（所选题目难度之和）在区间 $[l, r]$ 内：
- 总难度 $\ge l$；
- 总难度 $\le r$；
3. 所选题目中，**最难题的难度**与**最易题的难度**之差 **至少为 $x$**。
问：一共有多少种不同的**题集选择方法**满足上述所有条件？
输入格式
第一行包含四个整数 $n, l, r, x$：
- $1 \le n \le 15$ —— 题目的数量；
- $1 \le l \le r \le 10^9$ —— 题集总难度的下限和上限；
- $1 \le x \le 10^6$ —— 所选题目中“最大难度 − 最小难度”的下限。
第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 10^6$），表示每道题目的难度。
- $1 \le n \le 15$ —— 题目的数量；
- $1 \le l \le r \le 10^9$ —— 题集总难度的下限和上限；
- $1 \le x \le 10^6$ —— 所选题目中“最大难度 − 最小难度”的下限。
第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 10^6$），表示每道题目的难度。
输出格式
输出一个整数，表示为本次比赛选择一个**合适题集**的方法数。
输入输出样例
输入 #1
3 5 6 1 1 2 3
输出 #1
2
输入 #2
4 40 50 10 10 20 30 25
输出 #2
2
输入 #3
5 25 35 10 10 10 20 10 20
输出 #3
6
说明/提示
### 解释 #1
满足条件的集合有两种：
- 选择难度为 $\{2, 3\}$ 的题目，
- 选择难度为 $\{1, 2, 3\}$ 的题目。
### 解释 #2
满足条件的集合为：
- $\{10, 30\}$；
- $\{20, 30\}$。
### 解释 #3
任意由一题难度为 $10$ 和一题难度为 $20$ 组成的集合都是合适的（再加其他题，只要总难度仍在区间内，也可以）。
满足条件的集合有两种：
- 选择难度为 $\{2, 3\}$ 的题目，
- 选择难度为 $\{1, 2, 3\}$ 的题目。
### 解释 #2
满足条件的集合为：
- $\{10, 30\}$；
- $\{20, 30\}$。
### 解释 #3
任意由一题难度为 $10$ 和一题难度为 $20$ 组成的集合都是合适的（再加其他题，只要总难度仍在区间内，也可以）。