Hiểu bài toán

Cho hai số nguyên dương N và K. Ban đầu có một đàn bò gồm N con. Mỗi lần chia đàn bò, ta chọn một con bò có số lượng x và thay nó bằng 2 con bò mới có tổng số lượng bằng x và hiệu số lượng bằng K (tức là hai con có số lượng a, b sao cho a + b = x và |a - b| = K). Quá trình này lặp lại cho đến khi không thể chia thêm bất kỳ con bò nào (tức là không tồn tại hai số nguyên dương a, b thỏa mãn điều kiện). Yêu cầu找出 số lượng nhóm bò cuối cùng (số lượng con bò không thể chia tiếp).

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

Cách Quy hoạch động (Simulation)

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

int main() {
    int N, K;
    cin >> N >> K;

    int result = 0;
    queue<int> q;
    q.push(N);

    while (!q.empty()) {
        int x = q.front(); q.pop();

        // Kiem tra co the chia duoc khong
        if ((x + K) % 2 == 0) {
            int a = (x + K) / 2;
            int b = x - a;

            if (a > 0 && b > 0) {
                q.push(a);
                q.push(b);
                continue;
            }
        }

        // Khong chia duoc -> dem vao nhom cuoi cung
        result++;
    }

    cout << result;
    return 0;
}

• Time Complexity: O(N) trong trường hợp xấu nhất
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng trực tiếp quá trình chia đàn bò bằng cách sử dụng hàng đợi (queue). Ban đầu đưa N vào hàng đợi. Lặp trong khi hàng đợi còn phần tử: lấy một phần tử x ra, kiểm tra xem có thể chia x thành a và b thỏa mãn a + b = x và |a - b| = K hay không (tức là (x + K) phải chẵn và a, b > 0). Nếu được thì đẩy a và b vào hàng đợi, nếu không thì tăng biến đếm lên 1. Thuật toán dừng khi hàng đợi rỗng.

Cách Đệ quy

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

int n, k;
int dem = 0;

int trai(int x, int l) {
    return (x - l) / 2;
}

int phai(int x, int l) {
    return (x + l) / 2;
}

void dequy(int u, int v) {
    if (u - v <= 0 || (u - v) % 2 != 0) {
        dem++;
        return;
    }
    dequy(trai(u, v), v);
    dequy(phai(u, v), v);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    dequy(n, k);
    cout << dem;
    return 0;
}

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

Tiếp cận đệ quy quay lui. Hàm dequy(u, v) xử lý một con bò có số lượng u. Nếu u không thể chia (u - v <= 0 hoặc u - v là số lẻ) thì tăng biến đếm và dừng nhánh đó. Ngược lại, đệ quy gọi cho hai con mới: trai(u, v) = (u - v) / 2 và phai(u, v) = (u + v) / 2. Đây là cách suy nghĩ trực tiếp từ công thức a = (x + K)/2, b = (x - K)/2.

Cách Tối ưu (Toán học)

#include <iostream>
using namespace std;

int main() {
    long long N, K;
    cin >> N >> K;

    // Neu K >= N, khong the chia vi a, b phai duong
    if (K >= N) {
        cout << 1;
        return 0;
    }

    // Neu N va K cung dau (cung le hoac cung chan)
    // N - K phai la so chan de co a, b nguyen
    if ((N - K) % 2 != 0) {
        cout << 1;
        return 0;
    }

    // Tinh toan so luong nhom cuoi cung
    // Moi phep chia tang so luong bao len 1
    // Dung lai khi khong the chia nua
    // Cong thuc: so nhom = 2^k, khi N co the chia k lan
    // O day ta chi can dem so lan co the chia lien tuc

    long long count = 1;
    long long cur = N;
    while (true) {
        if (cur < K || (cur - K) % 2 != 0) break;
        long long a = (cur + K) / 2;
        long long b = cur - a;
        if (a <= 0 || b <= 0) break;
        // Tiep tuc chia
        cur = a; // Hoac b, cung chung 1 nhom
        count *= 2;
    }

    cout << count;
    return 0;
}

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

Tiếp cận tối ưu bằng cách quan sát quy luật. Mỗi lần chia thành công, số lượng con bò tăng lên gấp đôi (vì 1 con chia thành 2). Ta chỉ cần kiểm tra xem có thể chia bao nhiêu lần liên tiếp cho đến khi không thể chia nữa. Điều kiện dừng là khi con bò hiện tại nhỏ hơn K hoặc chênh lệch N - K là số lẻ. Số nhóm cuối cùng sẽ là 2^sốlầnchia.

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

Bài học kinh nghiệm

• Điều kiện chia một con bò x thành a, b: (x + K) phải chẵn và a, b > 0. Tức là x >= K+1 và x ≡ K (mod 2).
• Mỗi lần chia thành công, tổng số con bò tăng lên 1 (1 con thành 2 con).
• Nếu một con bò có thể chia, thì các con bò sinh ra sau đó cũng có thể chia tiếp nếu thỏa mãn điều kiện.

Lỗi thường gặp

• Quên kiểm tra a, b > 0 khi tính toán (ví dụ với K rất lớn).
• Sử dụng biến đệm sai kiểu (nguyên tố tràn số với N lớn).
• Lặp vô hạn trong cách đệ quy nếu không có điều kiện dừng đúng.