Hiểu bài toán

Bài toán yêu cầu tìm số lượng tờ tiền của các mệnh giá 20, 50, 100 sao cho tổng số tờ tiền là n và tổng giá trị của từng mệnh giá bằng nhau. Giả sử có a tờ 20, b tờ 50, c tờ 100. Điều kiện:

1. a + b + c = n (Tổng số tờ)
2. 20a = 50b = 100c (Tổng giá trị của mỗi mệnh giá bằng nhau) Từ điều kiện 2, ta có: 20a = 50b => 2a = 5b => a = 2.5b 20a = 100c => a = 5c Từ a = 5c và a = 2.5b => b = 2c. Vậy: a = 5c, b = 2c. Thay vào điều kiện 1: 5c + 2c + c = n => 8c = n. Vậy để có nghiệm nguyên dương, n phải chia hết cho 8. Nếu n chia hết cho 8, gọi k = n/8, ta có nghiệm: a = 5k, b = 2k, c = k. Nếu n không chia hết cho 8 hoặc n=0, không có nghiệm.

Các cách tiếp cận

Cách Phép chia và kiểm tra

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        // Kiểm tra n chia hết cho 8 và n khác 0
        if (n % 8 != 0 || n == 0) {
            cout << -1 << "\n";
        } else {
            // Tính số lượng theo công thức tìm được
            long long c = n / 8;
            long long b = 2 * c;
            long long a = 5 * c;
            cout << a << " " << b << " " << c << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Phương pháp này dựa trên việc suy ra công thức trực tiếp từ các điều kiện của bài toán.

1. Điều kiện tổng giá trị bằng nhau: 20a = 50b = 100c.
2. Rút gọn: 2a = 5b và a = 5c.
3. Suy ra tỉ lệ: c : b : a = 1 : 2 : 5.
4. Tổng số tờ n = a + b + c = 5c + 2c + c = 8c.
5. Kết luận: n phải chia hết cho 8. Nếu có, số lượng tờ là (5n/8, 2n/8, n/8).

Cách Thử nghiệm các giá trị c (Brute Force)

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        bool found = false;
        // Duyệt c từ 1 đến n/8 (hoặc n)
        // Thực tế chỉ cần duyệt c đến n/8
        for (long long c = 1; c * 8 <= n; ++c) {
            long long b = 2 * c;
            long long a = 5 * c;
            if (a + b + c == n) {
                cout << a << " " << b << " " << c << "\n";
                found = true;
                break;
            }
        }
        if (!found) cout << -1 << "\n";
    }
    return 0;
}

• Time Complexity: O(n) -> Quá chậm với n len 10^18
• Space Complexity: O(1)

Đây là cách tiếp cận mô phỏng lại logic bài toán bằng code. Biến đổi điều kiện: 20a + 50b + 100c = 0 (vì tổng giá trị 3 loại bằng nhau, đặt bằng V). 20a = 50b => a = 2.5b (a phải chia hết cho 5, b chia hết cho 2). 20a = 100c => a = 5c. Thay a = 5c vào a = 2.5b => b = 2c. Vậy a = 5c, b = 2c. Tổng số tờ: 5c + 2c + c = 8c = n. Vì n có thể lên tới 10^18, cách này không khả thi nếu duyệt toàn bộ. Tuy nhiên, nếu ta biết trước quan hệ tuyến tính (a=5c, b=2c), ta có thể kiểm tra trực tiếp n % 8 == 0 thay vì duyệt.

Cách Phương pháp kiểm tra chia hết (Optimized Logic)

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        if (n == 0) {
            cout << -1 << "\n";
            continue;
        }
        // Tính toán trực tiếp, Solution 1 style
        long long a = n / 8 * 5;
        long long b = n / 4;
        long long c = n / 8;

        // Kiểm tra chẵn lẻ và chia hết
        // Hoặc đơn giản là kiểm tra a+b+c == n
        if (a + b + c != n) cout << -1 << "\n";
        else cout << a << ' ' << b << ' ' << c << '\n';
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Đây là biến thể của phương pháp 1, sử dụng phép chia nguyên. Nếu n chia hết cho 8: c = n / 8 b = n / 4 (tương đương 2 * n / 8) a = 5 * (n / 8) Nếu n không chia hết cho 8, phép chia nguyên n/8 sẽ lấy phần nguyên, dẫn đến a+b+c != n. Do đó, kiểm tra a+b+c == n là một cách để kiểm tra n có chia hết cho 8 hay không. Ngoài ra, n=0 là trường hợp đặc biệt (chia hết cho 8 nhưng không có nghiệm dương).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Từ điều kiện tổng giá trị bằng nhau (20a = 50b = 100c), ta suy ra được tỉ lệ số lượng tờ tiền a : b : c = 5 : 2 : 1.
• Tổng số tờ tiền n = 8c. Do đó, nghiệm tồn tại nguyên dương khi và chỉ khi n chia hết cho 8 (và n > 0).

Lỗi thường gặp

• Quên kiểm tra trường hợp n = 0. Dù 0 chia hết cho 8, nhưng yêu cầu in số lượng nguyên dương nên n=0 không có nghiệm.
• Sử dụng biến kiểu int cho n (n có thể lên tới 10^18), gây tràn số.