Hiểu bài toán

Bài toán yêu cầu tìm số nhóm tối đa (mỗi nhóm gồm 2 ông táo và 1 bà táo) có thể tạo ra từ m ông táo và n bà táo, trong đó có tổng cộng k cá thể (ông hoặc bà) bị loại khỏi các nhóm này để làm nhiệm vụ đặc biệt. Cần tối đa hóa số nhóm, và k cá thể còn lại sau khi tạo nhóm sẽ được dùng để làm nhiệm vụ đặc biệt. Nói cách khác, tìm số nguyên không âm x (số nhóm) lớn nhất sao cho số cá thể còn lại sau khi tạo x nhóm (tổng cộng m + n - 3x) lớn hơn hoặc bằng k.

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

Cách Brute Force

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

int main() {
    long long m, n, k;
    cin >> m >> n >> k;
    long long max_theo_ong = m / 2;
    long long max_theo_ba = n;
    long long max_groups = min(max_theo_ong, max_theo_ba);

    for (long long x = max_groups; x >= 0; --x) {
        long long remaining = (m - 2 * x) + (n - x);
        if (remaining >= k) {
            cout << x << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

• Time Complexity: O(m/2) ~ O(m)
• Space Complexity: O(1)

Cách tiếp cận này thử tất cả các khả năng từ số nhóm lớn nhất có thể (giới hạn bởi số lượng ông táo và bà táo) giảm dần về 0. Số nhóm lớn nhất có thể là min(m/2, n). Với mỗi số nhóm x, ta kiểm tra xem có đủ cá thể còn lại (m + n - 3x) để thỏa mãn điều kiện có ít nhất k cá thể làm nhiệm vụ đặc biệt hay không. Vì min(m/2, n) có thể lên tới 10^9, cách này sẽ quá thời gian.

Cách Binary Search

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

int main() {
    long long m, n, k;
    cin >> m >> n >> k;
    long long left = 0;
    long long right = min(m / 2, n);
    long long ans = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        long long remaining = (m - 2 * mid) + (n - mid);
        if (remaining >= k) {
            ans = mid;
            left = mid + 1; // Thử tìm số nhóm lớn hơn
        } else {
            right = mid - 1; // Số nhóm quá lớn, phải giảm xuống
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(log(min(m/2, n))) ~ O(log(10^9))
• Space Complexity: O(1)

Bài toán có tính đơn điệu: Nếu ta có thể tạo được x nhóm, thì ta chắc chắn có thể tạo được y nhóm với mọi y < x (vì số lượng cá thể còn lại sẽ nhiều hơn). Do đó, ta có thể dùng kỹ thuật tìm kiếm nhị phân để tìm giá trị x lớn nhất thỏa mãn điều kiện m + n - 3x >= k. Biên trên của tìm kiếm nhị phân là min(m/2, n). Độ phức tạp logarithmic giúp giải quyết nhanh chóng ngay cả với input lớn.

Cách Direct Formula (Math)

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

int main() {
    long long m, n, k;
    cin >> m >> n >> k;
    // Số nhóm tối đa có thể về mặt lí thuyết
    long long max_possible = min(m / 2, n);

    // Số cá thể tối thiểu cần dùng cho x nhóm là 3*x
    // Số cá thể tối đa có thể "văng" ra là (m + n - 3*x)
    // Điều kiện: (m + n - 3*x) >= k  =>  3*x <= m + n - k

    long long limit_by_resources = (m + n - k) / 3;

    // Số nhóm thực tế là giá trị nhỏ nhất giữa giới hạn của nguyên liệu và giới hạn của công thức
    long long ans = min(max_possible, limit_by_resources);

    // Đảm bảo không âm (dù logic input dương thì ans vẫn dương)
    if (ans < 0) ans = 0;

    cout << ans << endl;
    return 0;
}

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

Đây là phương pháp tối ưu nhất. Ta có hai giới hạn cho số nhóm x:

1. Giới hạn về nguyên liệu: Ta cần 2 ông và 1 bà cho mỗi nhóm. Vậy số nhóm tối đa bị giới hạn bởi min(m/2, n).
2. Giới hạn về tổng số cá thể: Sau khi tạo x nhóm, còn lại m + n - 3x cá thể. Số này phải >= k. Trừ đi ta được 3x <= m + n - k, suy ra x <= (m + n - k) / 3. Số nhóm tối đa có thể tạo ra là giá trị nhỏ nhất của hai giới hạn trên. Phương pháp này tính toán trực tiếp bằng công thức toán học.

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

Bài học kinh nghiệm

• Bài toán có tính đơn điệu (monotonic): Nếu có thể tạo x nhóm thì có thể tạo < x nhóm. Điều này cho phép áp dụng Binary Search hoặc công thức toán học.
• Có hai ràng buộc chính: (1) Ràng buộc về số lượng từng loại (2 ông/bà mỗi nhóm) và (2) Ràng buộc về tổng số cá thể còn lại sau khi tạo nhóm.

Lỗi thường gặp

• Overflow số nguyên: Khi m, n, k lên tới 10^9, các phép tính như m + n có thể vượt quá giới hạn của kiểu int (khoảng 2 tỷ). Cần dùng long long (64-bit).
• Sai logic về số nguyên chia hết: Phép chia (m + n - k) / 3 là số nguyên dương (floor division), đảm bảo 3x <= m + n - k.
• Lầm tưởng về việc chọn cá thể đặc biệt: Ta không cần chọn cụ thể ai, chỉ cần đảm bảo tổng số cá thể còn lại >= k. Việc tối đa hóa số nhóm đồng nghĩa với tối thiểu hóa số cá thể được dùng (3x), do đó tối đa hóa số cá thể còn lại.