Hiểu bài toán

Bài toán yêu cầu tìm thời gian tối thiểu để rán n cái bánh, mỗi cái có 2 mặt. Một chảo có thể rán được k cái bánh cùng lúc. Mỗi lần rán một mặt bánh tốn 5 phút. Có thể lật bánh bất cứ lúc nào. Vấn đề cần giải quyết là tối ưu hóa việc sử dụng chảo để giảm thời gian chờ.

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

Cách Mô phỏng từng khoảng thời gian (Time Slicing)

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

int main() {
    int n, k;
    cin >> n >> k;
    int total_sides = 2 * n;
    int current_sides = 0;
    int time = 0;

    while (current_sides < total_sides) {
        // Trong 5 phút, chảo có thể rán tối đa k mặt
        int sides_to_fry = min(k, total_sides - current_sides);
        current_sides += sides_to_fry;
        time += 5;
    }

    cout << time;
    return 0;
}

• Time Complexity: O(total_sides / k) ~ O(n/k)
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng quá trình rán theo từng đợt 5 phút. Ở mỗi đợt, chúng ta rán tối đa k mặt bánh nếu còn bánh cần rán. Số lần lặp sẽ khoảng (2*n)/k. Đây là cách trực quan nhất để hiểu vấn đề.

Cách Tính toán trực tiếp bằng công thức

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

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

    if (n <= k) {
        // Nếu số bánh ít hơn hoặc bằng sức chứa chảo
        // Có thể rán cả 2 mặt của n cái bánh trong 2 lượt
        cout << 10;
    } else {
        long long total_sides = 2 * n;
        // Số lượt rán cần thiết = ceil(total_sides / k)
        long long batches = (total_sides + k - 1) / k;
        cout << batches * 5;
    }
    return 0;
}

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

Đây là cách tối ưu nhất. Tổng số mặt cần rán là 2n. Mỗi lần rán (5 phút) có thể xử lý tối đa k mặt. Số lượt cần thiết là ceil(2n / k). Công thức để tính ceil(a/b) trong integer là (a + b - 1) / b. Nếu n <= k, ta rán 2 lượt (10 phút).

Cách Công thức với xử lý trường hợp đặc biệt

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

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

    if (n <= k) {
        cout << 10;
    } else {
        long long a = 2 * n / k;
        long long du = 2 * n % k;
        if (du != 0) a++;
        cout << a * 5;
    }
    return 0;
}

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

Cách này chia nhỏ phép tính ceil. a = (2n)/k là phần nguyên, du = (2n)%k là phần dư. Nếu dư khác 0, ta cần thêm 1 lượt. Tuy nhiên, cách này có thể gây lỗi logic nếu n rất nhỏ (ví dụ n=1, k=1000, 2*n=2, k=1000, a=0, du!=0 => a=1 => 5 phút, nhưng thực tế cần 10 phút). Do đó cần kiểm tra n <= k trước.

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

Bài học kinh nghiệm

• Mỗi cái bánh có 2 mặt, nhưng chảo rán được k cái bánh cùng lúc (tức k mặt cùng lúc)
• Thời gian rán không phụ thuộc vào việc lật bánh mà phụ thuộc vào số lượng 'mặt-bánh' cần rán
• Bài toán quy về tìm số lượt rán (mỗi lượt 5 phút) để xử lý hết 2*n mặt với sức chứa k

Lỗi thường gặp

• Quên nhân đôi n lên để tính tổng số mặt (phải là 2*n)
• Sai công thức tính số lượt rán (lấy số nguyên thay vì số thực)
• Không xử lý đúng trường hợp n <= k (ví dụ n=1, k=1000)
• Làm tròn sai hướng (phải làm tròn lên, không làm tròn xuống)