Vòng tay

Tác giả:

Dạng bài

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Lê có \(n\) hạt cườm, hạt thứ \(i\) (\(1 \le i \le n\)) có mã màu là \(c_i\). Lê muốn chọn ra đúng \(m\) (\(m < n\)) hạt để làm một vòng tay. Vì rất yêu thích số \(s\) nên Lê muốn đếm xem có bao nhiêu cách chọn \(m\) hạt mà tổng giá trị các mã màu đúng bằng \(s\). Hai cách được gọi là khác nhau nếu tồn tại một hạt được chọn trong cách này nhưng không thuộc trong cách kia.

Yêu cầu: Cho các số nguyên dương \(c_1,c_2,...,c_n\) là mã màu của \(n\) hạt cườm và hai số nguyên dương \(m,s\), hãy đếm số cách chọn \(m\) hạt để tổng giá trị các mã màu của các hạt được chọn bằng \(s\).

Input

Dòng đầu tiên gồm ba số nguyên \(n,m,s\).
Dòng thứ hai chứa \(n\) số nguyên dương \(c_1,c_2,...,c_n\) (\(1 \le c_i \le 10^9\)).

Output

Một dòng chứa một số nguyên là số cách chọn thỏa mãn.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(m = n-1, n \le 18\).
Subtask \(2\) (\(40\%\) số điểm): \(n \le 18\).
Subtask \(3\) (\(30\%\) số điểm): \(n \le 36\).

Example

Test 1

Input

5 4 10
2 2 3 2 3

Output

Bình luận

hint

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Hàm tạo danh sách các tổng của các tổ hợp
void generateSubsets(const vector<int>& arr, vector<pair<int, int>>& subsets, int maxCount) {
    int n = arr.size();
    for (int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0, count = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                sum += arr[i];
                ++count;
            }
        }
        if (count <= maxCount) {
            subsets.push_back({sum, count});
        }
    }
}

// Hàm đếm số cách chọn
ll countWays(int n, int m, int s, const vector<int>& c) {
    int mid = n / 2;
    vector<int> left(c.begin(), c.begin() + mid);
    vector<int> right(c.begin() + mid, c.end());

    vector<pair<int, int>> leftSubsets, rightSubsets;
    generateSubsets(left, leftSubsets, m);
    generateSubsets(right, rightSubsets, m);

    // Sắp xếp danh sách rightSubsets theo tổng để binary search
    sort(rightSubsets.begin(), rightSubsets.end());

    ll result = 0;

    // Kiểm tra tất cả các tổ hợp từ leftSubsets
    for (const auto& [leftSum, leftCount] : leftSubsets) {
        if (leftCount > m) continue;

        int target = s - leftSum;
        int requiredCount = m - leftCount;

        // Tìm các tập hợp từ rightSubsets sao cho tổng bằng target và số lượng đúng
        auto range = equal_range(
            rightSubsets.begin(), rightSubsets.end(),
            make_pair(target, requiredCount),
            [](const pair<int, int>& a, const pair<int, int>& b) {
                return (a.first < b.first) || (a.first == b.first && a.second < b.second);
            }
        );
        result += distance(range.first, range.second);
    }

    return result;
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];

    cout << countWays(n, m, s, c) << endl;
    return 0;
}

n,m,s=map(int, input(). split())
c1,c2,c3,c4,cn=map(int, input(). split())

Rồi gì nữa giúp tui

0

p12b4PhamNgocThaiBao 4:37 p.m. 26 Tháng 10, 2024 ← đã chỉnh sửa →

Giúp tui trên đây

0

sondang0914 8:18 p.m. 23 Tháng 10, 2024

khó vãi cức

0

sondang0914 8:43 a.m. 20 Tháng 10, 2024

help me

0

tranphuongliem 10:45 a.m. 21 Tháng 7, 2024

dqcn là đc

4

Dang_Minh_Duc 9:59 p.m. 20 Tháng 7, 2024

Duyệt phân tập (Meet-in-the-middle) là AC nha

1 phản hồi