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

nguyentienthach2009 • 9:08 p.m. 1 Tháng 12, 2024 •

Nhánh cận là được 19 test, còn dùng Meet in the Middle (MITM) hay được gọi là kỹ thuật phân chia và chinh phục (Divide and Conquer) hoặc bitmask là AC được:), bài đây nhánh cận thui là đủ rùi chứ cách còn lại hơi khó.

0
Phản hồi Chia sẻ

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

Phản hồi

p12b4PhamNgocThaiBao • 4:39 p.m. 26 Tháng 10, 2024 •
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
Phản hồi Chia sẻ

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

Giúp tui trên đây

0
Phản hồi Chia sẻ

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

khó vãi cức

-1
Phản hồi Chia sẻ

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

help me

0
Phản hồi Chia sẻ

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

dqcn là đc

0
Phản hồi Chia sẻ

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

4
Phản hồi Chia sẻ

1 phản hồi