Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Xét một hệ thống tiền tệ bao gồm � n loại mệnh giá đồng xu. Mỗi đồng xu có giá trị…

  1. User

    Xét một hệ thống tiền tệ bao gồm � n loại mệnh giá đồng xu. Mỗi đồng xu có giá trị nguyên dương. Nhiệm vụ của bạn là tính số cách phân biệt để tạo ra một tổng tiền � x sử dụng các đồng xu có sẵn. Ví dụ, nếu các mệnh giá đồng xu là { 2 , 3 , 5 } {2,3,5} và tổng tiền mong muốn là 9 9, có 3 3 cách: 2 + 2 + 5 2+2+5 3 + 3 + 3 3+3+3 2 + 2 + 2 + 3 2+2+2+3 Đầu vào Dòng 1: gồm hai số nguyên � n và � x: số lượng mệnh giá đồng xu và tổng tiền mong muốn. Dòng 2: gồm � n số nguyên phân biệt � 1 , � 2 , … , � � c 1 ​ ,c 2 ​ ,…,c n ​ : giá trị của mỗi mệnh giá đồng xu. Đầu ra In ra một số nguyên: số cách tạo ra tổng tiền theo thứ tự đặc biệt, lấy modulo 1 0 9 + 7 10 9 +7. Ràng buộc 1 ≤ � ≤ 100 1≤n≤100 1 ≤ � ≤ 1 0 6 1≤x≤10 6 1 ≤ � � ≤ 1 0 6 1≤c i ​ ≤10 6 lap trinh c++

  2. Assistant

    Dùng phương pháp Quy hoạch động để giải bài toán này.

    Gọi DP[i] là số cách tạo ra tổng tiền i sử dụng các đồng xu có sẵn.

    DP[i] có thể được tính như sau:

    • Với mỗi loại đồng xu có giá trị là v, nếu i >= v, ta có thể thêm đồng xu v vào các cách tạo ra tổng tiền i - v để có thêm cách tạo ra tổng tiền i. Do đó, ta cập nhật DP[i] bằng cách cộng DP[i - v] với DP[i].

    Với mỗi giá trị của i từ 1 đến x, ta tính DP[i] theo cách trên. Cuối cùng, DP[x] chính là số cách tạo ra tổng tiền x.

    Dưới đây là mã giả của thuật toán:

    int mod(int n) { return (n % 1000000007 + 1000000007) % 1000000007; }

    int countWays(int n, int x, int coins[]) { int DP[x + 1]; memset(DP, 0, sizeof(DP));

    DP[0] = 1; // Có 1 cách tạo ra tổng tiền 0, không sử dụng đồng xu nào
    
    for (int i = 1; i <= x; i++) {
        for (int j = 0; j < n; j++) {
            if (i >= coins[j]) {
                DP[i] = mod(DP[i] + DP[i - coins[j]]);
            }
        }
    }
    
    return DP[x];
    

    }

    Độ phức tạp thời gian của thuật toán là O(n*x), với n là số lượng mệnh giá đồng xu và x là tổng tiền mong muốn.

  3. User

    hãy viết code từ mã giả

  4. Assistant

    Dưới đây là code C++ hoàn chỉnh dựa trên mã giả trên:

    #include <iostream>
    using namespace std;
    
    const int MOD = 1000000007;
    
    int countWays(int n, int x, int coins[]) {
        int DP[x + 1];
        memset(DP, 0, sizeof(DP));
    
        DP[0] = 1; // Có 1 cách tạo ra tổng tiền 0, không sử dụng đồng xu nào
    
        for (int i = 1; i <= x; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= coins[j]) {
                    DP[i] = (DP[i] + DP[i - coins[j]]) % MOD;
                }
            }
        }
    
        return DP[x];
    }
    
    int main() {
        int n, x;
        cin >> n >> x;
    
        int coins[n];
        for (int i = 0; i < n; i++) {
            cin >> coins[i];
        }
    
        int ways = countWays(n, x, coins);
        cout << ways << endl;
    
        return 0;
    }
    

    Bạn có thể chạy mã này để kiểm tra kết quả cho các bộ test khác nhau. Hãy nhập dữ liệu đầu vào theo đúng định dạng được mô tả trong đề bài.