preparing-olympiad

Preparing Olympiad

Codeforces medium

لديك \(n\) مسألة، وصعوبة المسألة رقم \(i\) هي \(c_i\). تريد أن تختار مجموعة من المسائل لمسابقة بحيث:

تحتوي المجموعة على مسألتين على الأقل،
لا تقل الصعوبة الكلية عن \(l\) ولا تزيد عن \(r\)،
لا يقل الفرق بين صعوبة أصعب مسألة مختارة وأسهل مسألة مختارة عن \(x\).

أوجد عدد الطرق لاختيار مثل هذه المجموعة.

القيود:

\(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\)

الإدخال:

السطر الأول: أربعة أعداد صحيحة \(n\) و \(l\) و \(r\) و \(x\).
السطر الثاني: \(n\) عددًا \(c_1, c_2, \dots, c_n\).

المخرجات:

عدد صحيح واحد — عدد المجموعات المناسبة.

أمثلة:

الإدخال:

3 5 6 1
1 2 3

المخرجات:

(المجموعتان المناسبتان هما \(\{2, 3\}\) و \(\{1, 2, 3\}\).)

الإدخال:

5 25 35 10
10 10 20 10 20

المخرجات:

(أي مجموعة تتكوّن من مسألة صعوبتها \(10\) ومسألة صعوبتها \(20\) مناسبة.)

الحل

يوجد \(2^n \le 2^{15} = 32768\) مجموعة جزئية فقط من المسائل، لذلك نفحص كل واحدة منها، كما في درس توليد المجموعات الجزئية.

لكل مجموعة جزئية نحسب الصعوبة الكلية وأسهل صعوبة وأصعب صعوبة، ونفحص شرط الصعوبة الكلية وشرط الفرق.

لا نحتاج إلى فحص حجم المجموعة بشكل منفصل: المجموعة التي فيها مسألة واحدة فرقها \(0\)، والمجموعة الفارغة فرقها \(0 - 10^6 < 0\) مع القيم الابتدائية في الكود. وبما أن \(x \ge 1\)، فإن شرط الفرق يرفض الحالتين.

الصعوبة الكلية لا تزيد عن \(15 \cdot 10^6\)، لذلك يكفي النوع int. يعمل الحل كله في زمن \(O(2^n \cdot n)\).

#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";
}