Hiểu bài toán

Bài toán yêu cầu tìm số phút tối thiểu để chiên chín n con cá bằng một chiếc chảo có dung tích tối đa k con cá mỗi lần. Mỗi con cá có 2 mặt và cần 1 phút để chiên chín một mặt. Để ăn được một con cá, cả hai mặt của nó đều phải chín. Vấn đề là tối ưu hóa thời gian sử dụng chảo sao cho tổng thời gian là nhỏ nhất.

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

Cách Mô phỏng từng phút (Brute Force)

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    // Trong 1 phút, chảo có thể chiên tối đa k mặt cá
    // Tổng số mặt cá cần chiên là 2*n
    // Nếu 2*n <= k, ta chỉ cần 2 phút (mỗi mặt 1 phút)
    if (2 * n <= k) {
        cout << 2;
        return 0;
    }

    // Nếu không, cần ceil(2*n / k) phút
    int total_faces = 2 * n;
    int minutes = (total_faces + k - 1) / k;
    cout << minutes;

    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Ta tính tổng số mặt cá cần chiên (2n). Chảo có thể chiên tối đa k mặt cá mỗi phút. Nếu 2n <= k, ta có thể chiên hết các mặt trong 2 phút (vì mỗi con cá phải chiên ít nhất 2 phút, không thể làm chín cả 2 mặt cùng lúc trừ khi k đủ lớn). Nếu không, ta cần số nguyên lớn nhất không vượt quá (2*n)/k, tức là phép chia lấy trần. Công thức (2*n + k - 1) / k trong C++ là cách tính số nguyên trần của phân số.

Cách Công thức Toán học tối ưu

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    if (n <= k) {
        cout << 2;
    } else {
        // Tính tổng số mặt cá: 2 * n
        // Chia lấy trần cho k
        long long a = 2 * n / k;
        long long du = 2 * n % k;
        if (du != 0) a++;
        cout << a;
    }
    return 0;
}

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

Cách này tách biệt trường hợp đặc biệt (n <= k) ra. Logic cơ bản giống cách 1: chia tổng số mặt cá cho dung tích chảo. Nếu có dư (du != 0), ta cộng thêm 1 phút. Nếu n <= k, ta có thể đặt tất cả cá vào chảo, chiên mặt 1 trong phút 1, lật cá và chiên mặt 2 trong phút 2, t tổng cộng 2 phút.

Cách Vòng lặp mô phỏng (Simulation)

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    if (n <= k) {
        cout << 2;
        return 0;
    }

    int t = 2 * n; // Tổng số mặt cá
    int dem = 0;
    while (t > 0) {
        t -= k; // Mỗi phút chiên k mặt
        ++dem;
    }
    cout << dem;
    return 0;
}

• Time Complexity: O(2*n/k)
• Space Complexity: O(1)

Đây là cách tiếp cận mô phỏng thực tế. Ta giả sử có một danh sách các mặt cá cần chiên. Mỗi phút, ta làm chín k mặt cá (trừ đi k từ biến t). Ta đếm số lần lặp cho đến khi t <= 0. Độ phức tạp phụ thuộc vào n và k nhưng vẫn rất nhanh với giới hạn 500. Đây là cách dễ hiểu nhất về mặt mô phỏng hành động chiên cá.

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

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán chia cặp: tổng số 'mặt cá' cần chiên là 2*n.
• Chảo hoạt động như một bộ lọc băng thông: mỗi phút nó xử lý tối đa k đơn vị công việc (mặt cá).
• Điều kiện dừng đặc biệt: Nếu n <= k, ta luôn cần 2 phút (không thể chiên cả 2 mặt của 1 con cá trong cùng 1 phút vì cần lật cá).

Lỗi thường gặp

• Quên nhân đôi n lên (phải là 2*n thay vì n) vì mỗi con cá có 2 mặt.
• Sai công thức làm tròn số nguyên: cần dùng phép chia lấy trần (ceil) thay vì round hoặc floor. Ví dụ: 5/2 = 2.5 -> 3 phút.
• Xử lý sai trường hợp n <= k: nếu n=1, k=1, output là 2 (không phải 1).