Hiểu bài toán

Bài toán yêu cầu chia M viên kẹo cho N người xếp hàng theo thứ tự từ người nhỏ nhất (thấp nhất) đến người lớn nhất (cao nhất) sao cho:

1. Mỗi người đều có ít nhất 1 viên kẹo.
2. Người đứng trước (nhỏ hơn) không được nhận ít kẹo hơn người đứng sau (lớn hơn), tức là số kẹo phải giảm dần (hoặc bằng) từ trái sang phải.

Cần thực hiện 2 việc:

1. Đếm tổng số cách chia kẹo thỏa mãn.
2. Tìm một cách chia sao cho chênh lệch giữa số kẹo của người nhận nhiều nhất (người đầu tiên) và người nhận ít nhất (người cuối cùng) là nhỏ nhất có thể.

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

Cách Quay lui (Backtracking) - Duyệt tất cả tổ hợp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
vector<vector<int>> v; // Lưu các cách chia
int sum = 0;
int x[1005]; // Mảng lưu cách chia hiện tại

void chuyen() {
    vector<int> tmp;
    for (int j = 1; j <= n; j++) {
        tmp.push_back(x[j]);
    }
    v.push_back(tmp);
}

// Thử các giá trị cho người thứ i, với giá trị không vượt quá pos
void Try(int i, int pos) {
    for (int j = pos; j >= 1; j--) {
        x[i] = j;
        sum += j;
        if (sum == k && i == n) {
            chuyen(); // Tìm thấy một cách chia hợp lệ
        } else if (sum < k && i < n) {
            Try(i + 1, j); // Quay lui cho người tiếp theo
        }
        sum -= j; // Backtrack
    }
}

int main() {
    cin >> n >> k;
    Try(1, k); // Bắt đầu từ người thứ 1, giá trị tối đa là k
    cout << v.size() << endl;
    // In ra cách chia cuối cùng (thường là cách chia đều nhất)
    for (int i = 0; i < v[v.size() - 1].size(); i++) cout << v[v.size() - 1] << " ";
}

• Time Complexity: O(C(M-1, N-1)) ~ O(M^(N-1))
• Space Complexity: O(C(M-1, N-1))

Phương pháp này sử dụng kỹ thuật quay lui (Backtracking) để tạo ra tất cả các dãy số thỏa mãn.

• Hàm Try(i, pos) tìm giá trị cho người thứ i.
• Biến pos giới hạn giá trị lớn nhất của người hiện tại để đảm bảo dãy giảm dần (người trước >= người sau).
• Vòng lặp for (int j = pos; j >= 1; j--) thử tất cả các giá trị từ pos trở xuống.
• Điều kiện dừng: khi đã chia đủ n người (i == n) và tổng kẹo bằng k.
• Sau khi chạy xong, v.size() cho số cách chia. Code in ra cách chia cuối cùng trong danh sách, nhưng cách này không đảm bảo cách in ra có chênh lệch nhỏ nhất trừ khi ta kiểm tra lại toàn bộ.

Cách Quay lui có tối ưu (Tìm min chênh lệch)

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

long long a[1000009], n, i, k, s[1000009], maxx = LLONG_MAX, check = 0;
vector<long long> v(502); // Mảng lưu cách chia hiện tại
vector<long long> q(502); // Mảng lưu cách chia có chênh lệch nhỏ nhất

void bbq(long long i, long long sum, long long bigboy) {
    if (i > n) {
        if (sum == k) {
            // Kiểm tra và cập nhật cách chia tốt nhất
            if (v[1] - v[n] < maxx) {
                maxx = v[1] - v[n];
                q = v;
            }
            check++; // Đếm số cách
        }
        return;
    }
    if (i == n) {
        // Người cuối cùng nhận phần còn lại
        if (k - sum <= bigboy && k - sum != 0) {
            v[i] = k - sum;
            bbq(i + 1, k, k - sum);
        }
        return;
    }
    // Thử các giá trị cho người thứ i
    for (long long j = min(bigboy, k - sum); j >= 1; j--) {
        v[i] = j;
        bbq(i + 1, j + sum, min(bigboy, j));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    bbq(1, 0, k);
    cout << check << "\n";
    for (i = 1; i <= n; i++) cout << q[i] << " ";
    return 0;
}

• Time Complexity: O(C(M-1, N-1))
• Space Complexity: O(N)

Đây là biến thể của Quay lui, được tối ưu để giải quyết yêu cầu thứ 2 (tìm min chênh lệch).

• Hàm bbq giống với Try nhưng truyền thêm tham số bigboy để giới hạn giá trị tối đa của người tiếp theo.
• Biến toàn cục maxx lưu chênh lệch nhỏ nhất tìm được.
• Biến q lưu dãy số tương ứng.
• Trong mỗi lần tìm thấy một cách chia hợp lệ (đến cuối dãy và tổng bằng k), ta tính v[1] - v[n]. Nếu nhỏ hơn maxx, ta cập nhật maxx và sao chép dãy v vào q.
• Cách này vẫn duyệt qua tất cả các cách chia (complexity xấp xỉ như cách 1) nhưng đảm bảo tìm được phương án tối ưu về chênh lệch.

Cách Dynamic Programming (Quy hoạch động)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    long long dp[25][55] = {0};
    dp[0][0] = 1;

    // Tính số cách chia
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            long long cach1 = 0;
            if (j >= 1) cach1 = dp[i - 1][j - 1]; // Case 1: Người đầu tiên có 1 kẹo
            long long cach2 = 0;
            if (j >= i) cach2 = dp[i][j - i];     // Case 2: Mỗi người có thêm 1 kẹo
            dp[i][j] = cach1 + cach2;
        }
    }
    cout << dp[N][M] << endl;

    // ... (Phần tìm cách chia chi tiết thường được xử lý bằng cách dựng lại quá trình DP)
    // Tuy nhiên, code mẫu bị cắt ngang nên phần này không đầy đủ.
    // Công thức DP: dp[i][j] = dp[i-1][j-1] + dp[i][j-i]
    // Ý nghĩa: 
    // dp[i-1][j-1]: Giả sử người đầu tiên lấy 1 kẹo, chia j-1 kẹo cho i-1 người còn lại.
    // dp[i][j-i]: Giả sử mỗi người đều lấy thêm 1 kẹo (tổng cộng i kẹo), chia j-i kẹo còn lại cho i người.
    // (Phương pháp này đếm số cách, nhưng việc tìm cách chia có chênh lệch nhỏ nhất qua DP hơi phức tạp để thể hiện ngắn gọn).

    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Sử dụng quy hoạch động để đếm số cách chia.

• dp[i][j] là số cách chia j kẹo cho i người.
• Công thức truy hồi:
  1. Người đầu tiên lấy 1 kẹo: Còn lại j-1 kẹo chia cho i-1 người -> dp[i-1][j-1].
  2. Người đầu tiên lấy nhiều hơn 1 kẹo: Để đảm bảo dãy giảm dần, ta có thể coi tất cả i người đều lấy thêm 1 kẹo (trừ đi i kẹo), chia j-i kẹo còn lại cho i người -> dp[i][j-i].
• Phương pháp này rất hiệu quả để đếm số cách (complexity O(NM)), nhưng để in ra dãy số cụ thể có chênh lệch nhỏ nhất, ta thường cần kết hợp với việc dựng lại dãy số từ bảng DP hoặc dùng Backtracking để tìm dãy tối ưu.

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

Bài học kinh nghiệm

• Vấn đề có thể được mô hình hóa như tìm các dãy số dương (a_1, a_2, ..., a_N) sao cho a_1 >= a_2 >= ... >= a_N và tổng bằng M.
• Đếm số cách chia kẹo tương đương với bài toán 'Phân tích số M thành tổng của N số nguyên dương' (Composition of an integer) nhưng có thêm ràng buộc thứ tự giảm dần.
• Để tìm cách chia có chênh lệch nhỏ nhất, ta có thể ưu tiên các giá trị gần nhau nhất. Trong Quay lui, việc cập nhật min/max ngay khi tìm được kết quả hợp lệ là cách trực tiếp nhất.

Lỗi thường gặp

• Quên kiểm tra điều kiện i == n và sum == k cùng lúc trong Quay lui, dẫn đến việc đếm sai hoặc truy cập ngoài mảng.
• Nếu chỉ in ra dãy số đầu tiên tìm được (hoặc cuối cùng trong mảng lưu), ta không đảm bảo đó là dãy có chênh lệch nhỏ nhất. Cần phải so sánh và lưu lại dãy tối ưu.
• Sử dụng biến int cho số cách chia có thể bị tràn số (overflow) nếu M và N lớn hơn một chút, mặc dù với giới hạn N <= 20, M <= 50 thì long long là an toàn.