Hiểu bài toán

Cho ~a~ bạn nữ, ~b~ bạn nam và ~c~ sinh viên bị loại (không tham gia thi). Mỗi đội thi cần 1 nam và 2 nữ. Ban tổ chức chọn ~c~ người bị loại sao cho số đội còn lại tạo được là lớn nhất. Cần tính số đội tối đa có thể thành lập.

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

Cách Công thức trực tiếp (Phân tích toán học)

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    // Số lượng người còn lại sau khi loại c người
    long long remaining = a + b - c;

    // Số đội tối đa theo giới hạn tổng số người (mỗi đội 3 người)
    long long limit_by_total = remaining / 3;

    // Số đội tối đa theo giới hạn số nam
    long long limit_by_males = b;

    // Số đội tối đa theo giới hạn số nữ (mỗi đội 2 nữ)
    long long limit_by_females = a / 2;

    // Kết quả là giá trị nhỏ nhất trong 3 giới hạn trên
    cout << min({limit_by_total, limit_by_males, limit_by_females});

    return 0;
}

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

Đây là phương pháp hiệu quả nhất. Ta nhận thấy số đội bị giới hạn bởi 3 yếu tố:

1. Tổng số người còn lại: remaining / 3
2. Số lượng nam giới: b
3. Số lượng nữ giới: a / 2

Tuy nhiên, có một điểm đặc biệt trong bài toán này là số lượng nam giới bị loại phụ thuộc vào số lượng nữ giới bị loại và ngược lại (vì tổng số người bị loại là c cố định). Nhưng may mắn thay, công thức (a + b - c) / 3 đã bao hàm việc tối ưu hóa số lượng nam/nữ còn lại. Đây là bài toán 'đóng gói' (bin packing) đơn giản với các ràng buộc ràng buộc lẫn nhau. Chỉ cần tính toán 3 giới hạn và lấy giá trị nhỏ nhất là ra kết quả.

Cách Tối ưu hóa bằng cách kiểm tra thủ công

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    // Cách tiếp cận 1: Dùng công thức tổng quát
    long long ans1 = min(a / 2, b);
    ans1 = min(ans1, (a + b - c) / 3);

    cout << ans1 << endl;

    return 0;
}

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

Đây là cách tiếp cận tương tự giải pháp 3 trong danh sách. Logic là:

1. Số đội không thể vượt quá min(a/2, b) do giới hạn nguyên liệu (2 nữ/đội, 1 nam/đội).
2. Số đội không thể vượt quá (a + b - c) / 3 do giới hạn tổng số người.

Tuy nhiên, cần lưu ý rằng min(a/2, b) là giới hạn của tổng số người ban đầu, chưa loại trừ c. Vì vậy, cách đúng là phải dùng (a + b - c) / 3 kết hợp với giới hạn nguyên liệu còn lại sau khi loại. Nhưng trong bài toán này, do c được chọn tối ưu, (a + b - c) / 3 thường là ràng buộc chính.

Giải pháp của K35Ti_Quoc_Anh thực ra chưa hoàn toàn chính xác nếu xét kỹ các trường hợp biên, nhưng lại qua được test do tính chất của dữ liệu. Giải pháp chuẩn là lấy min của 3 thành phần: giới hạn tổng người, giới hạn nam, giới hạn nữ.

Cách Tối ưu hóa bằng Binary Search (Tìm kiếm nhị phân)

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    // Binary search cho số đội (x)
    long long left = 0, right = (a + b - c) / 3;
    long long ans = 0;

    while (left <= right) {
        long long mid = (left + right) / 2;

        // Kiểm tra xem có thể tạo ra 'mid' đội không?
        // Cần: mid nam, 2*mid nữ.
        // Người bị loại: c người. Để tối ưu, ta nên loại ít nam/nữ nhất có thể.
        // Nếu mid <= b và mid*2 <= a, thì có thể.
        // Nhưng c có thể lớn hơn (a+b) - 3*mid.

        // Số người tối thiểu cần để tạo mid đội là 3*mid.
        // Nếu a + b - c >= 3*mid, tức là số người còn lại đủ.
        // Lúc này ta chỉ cần kiểm tra xem có đủ nam/nữ không.
        // Nhưng 'c' được chọn tối ưu, nên nếu tổng người đủ, ta có thể chọn loại người để giữ lại đủ nam/nữ.
        // Ràng buộc thực sự là: số nam còn lại >= mid, số nữ còn lại >= 2*mid.
        // Để tối ưu, ta nên giữ lại bao nhiêu nam? Nếu b >= mid, ta giữ mid nam. Nếu b < mid, fail.
        // Tương tự nữ.
        // Tuy nhiên, do c được chọn tối ưu, ta chỉ cần kiểm tra:
        // Có đủ người để tạo mid đội không? (a+b-c >= 3*mid)
        // Và có đủ nam không? (b >= mid)
        // Và có đủ nữ không? (a >= 2*mid)
        // Nhưng c có thể loại cả nam lẫn nữ.
        // Nếu b < mid hoặc a < 2*mid => fail.
        // Nếu a+b-c >= 3*mid => success.

        if (mid <= b && mid * 2 <= a && (a + b - c) >= 3 * mid) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

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

• Time Complexity: O(log(a+b))
• Space Complexity: O(1)

Binary search tìm số đội tối đa X. Điều kiện để thành lập được X đội:

1. Số nam còn lại >= X.
2. Số nữ còn lại >= 2X.
3. Tổng số người còn lại >= 3X.

Vì c được chọn tối ưu, ta chỉ cần đảm bảo các ràng buộc trên được thỏa mãn.

• Ràng buộc 3 (tổng người) là bắt buộc: (a + b - c) >= 3X.
• Ràng buộc 1 và 2 (nam/nữ) ta có thể kiểm tra trực tiếp từ a và b vì ta có thể chọn loại người để giữ lại nam/nữ nếu tổng người cho phép.

Nếu (a + b - c) >= 3X và b >= X và a >= 2X thì X là số đội hợp lệ. Tìm giá trị lớn nhất của X.

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

Bài học kinh nghiệm

• Số đội bị giới hạn bởi 3 yếu tố: tổng số người còn lại (chia cho 3), số lượng nam giới, và số lượng nữ giới (chia cho 2).
• Vì c người bị loại được chọn tối ưu để tối đa hóa số đội, ta chỉ cần chia tổng số người còn lại cho 3, nhưng vẫn phải đảm bảo không vượt quá giới hạn nguyên liệu (nam/nữ).
• Bài toán có thể giải bằng một công thức trực tiếp O(1) thay vì các thuật toán phức tạp.

Lỗi thường gặp

• Quên chia 3 cho tổng số người hoặc chia số nữ cho 2.
• Sử dụng số nguyên thông thường (int) thay vì số nguyên lớn (long long)导致 overflow vì a, b có thể lên tới 10^12.
• Lầm tưởng rằng cần phải tối ưu hóa số lượng nam/nữ bị loại cụ thể, trong khi việc lấy Min của các giới hạn là đủ do tính chất tối ưu của việc chọn người loại.