Preparing Olympiad
You have \(n\) problems, and the difficulty of the \(i\)-th problem is \(c_i\). You want to choose a set of problems for a contest such that:
- the set has at least two problems,
- the total difficulty is at least \(l\) and at most \(r\),
- the difference between the difficulties of the hardest and the easiest chosen problem is at least \(x\).
Find the number of ways to choose such a set.
Constraints:
- \(1 \le n \le 15\)
- \(1 \le l \le r \le 10^9\)
- \(1 \le x \le 10^6\)
- \(1 \le c_i \le 10^6\)
Input:
- First line: four integers \(n\), \(l\), \(r\), \(x\).
- Second line: \(n\) integers \(c_1, c_2, \dots, c_n\).
Output:
- One integer — the number of suitable sets.
Examples:
Input:
3 5 6 1
1 2 3
Output:
2
(The suitable sets are \(\{2, 3\}\) and \(\{1, 2, 3\}\).)
Input:
5 25 35 10
10 10 20 10 20
Output:
6
(Any set of one problem with difficulty \(10\) and one problem with difficulty \(20\) is suitable.)
Solution
There are only \(2^n \le 2^{15} = 32768\) subsets of problems, so we check each of them, as in the lesson on generating subsets.
For each subset we compute the total difficulty, the easiest difficulty, and the hardest difficulty, and check the conditions on the total and on the difference.
We do not need to check the size of the set separately: a set with one problem has difference \(0\), and the empty set has difference \(0 - 10^6 < 0\) with the initial values in the code. Since \(x \ge 1\), the condition on the difference rejects both.
The total difficulty is at most \(15 \cdot 10^6\), so int is enough. The whole solution takes \(O(2^n \cdot n)\) time.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, l, r, x;
cin >> n >> l >> r >> x;
int c[15];
for (int i = 0; i < n; i++) {
cin >> c[i];
}
int ways = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int total = 0;
int easiest = 1000000;
int hardest = 0;
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) {
total += c[j];
easiest = min(easiest, c[j]);
hardest = max(hardest, c[j]);
}
}
if (l <= total && total <= r && hardest - easiest >= x) {
ways++;
}
}
cout << ways << "\n";
}