Hiểu bài toán

Bài toán yêu cầu đếm số cách chia N viên kẹo cho 3 anh em (Hiếu, Kiệt, Hoàng) sao cho: 1) Tổng số kẹo bằng N; 2) Hiếu có ít nhất, Hoàng có nhiều nhất; 3) Số kẹo của 3 người khác nhau hoàn toàn và ai cũng có ít nhất 1 viên. Gọi số kẹo của Hiếu là a, Kiệt là b, Hoàng là c. Ta có a + b + c = N, với điều kiện 1 ≤ a < b < c. Bài toán quy về tìm số bộ (a, b, c) dương nguyên thỏa mãn.

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

Cách Công thức truy cập trực tiếp (O(1))

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n < 6) {
        cout << 0 << endl;
        return 0;
    }
    long long k = n / 3;
    long long ans = (k * (k - 1)) / 2;
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Với n ≥ 6, số cách chia bằng số cặp nguyên dương (a, b) thỏa mãn a < b và a + b < n - a (tức 2b < n - a). Dựa trên phân tích, số cách chia này được tổng quát hóa bằng công thức: floor(n/3) * (floor(n/3) - 1) / 2. Đây là cách hiệu quả nhất, xử lý ngay lập tức với mọi N ≤ 3×10^7.

Cách Tối ưu hóa vòng lặp (O(N))

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long res = 0;
    for (long long a = 1; a <= (n - 3) / 3; ++a){
        long long pmax = (n - 3*a - 1) / 2;
        if (pmax >= 1) res += pmax;
    }
    cout << res;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Phương pháp này dùng một vòng lặp để duyệt qua từng giá trị của a (số kẹo của Hiếu). Với mỗi a, ta tính số giá trị tối đa của b có thể có, bằng cách giải bất phương trình a < b < c. Cụ thể, b最大 là floor((n - 3a - 1)/2). Nếu giá trị này >= 1, ta cộng dồn vào kết quả. Vòng lặp chạy tối đa ~N/3 lần, chấp nhận được với N=30 triệu.

Cách Brute Force (O(N^2))

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long res = 0;
    for (long long a = 1; a < n; ++a) {
        for (long long b = a + 1; b < n; ++b) {
            long long c = n - a - b;
            if (c > b) {
                res++;
            }
        }
    }
    cout << res;
}

• Time Complexity: O(N^2)
• Space Complexity: O(1)

Đây là cách tiếp cận ngây thơ nhất, duyệt qua tất cả các cặp (a, b) và kiểm tra xem c = n - a - b có thỏa mãn c > b không. Độ phức tạp O(N^2) khiến nó quá chậm cho N lớn, chỉ mang tính chất minh họa.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán đếm số cặp (a, b) dương nguyên thỏa mãn a < b và a + b < N - a.
• Với N >= 6, công thức quy nạp cho số cách chia là: floor(N/3) * (floor(N/3) - 1) / 2.
• Biến đổi bất đẳng thức a < b < c với a+b+c=N dẫn đến giới hạn trên cho a là (N-3)/3.

Lỗi thường gặp

• Quên kiểm tra điều kiện N < 6, trường hợp này không có cách chia nào.
• Sử dụng biến kiểu int gây tràn số (overflow) khi N lên tới 30 triệu, cần dùng kiểu long long.
• Lỗi logic trong việc tính toán cận dưới/cận trên của các biến a, b, c.