← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6276 | 组题目

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

你有 $n$ 道题目，第 $i$ 道题目的难度为整数 $c_i$。
现在你想从中选出一些题目，用来组成一次比赛的题集。

这个题集要满足以下条件：

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
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
C++ 编辑器
输入
输出