Hiểu bài toán

Một cột đèn có thể chiếu sáng tối đa 4 ô vuông xung quanh nó (trên, dưới, trái, phải). Mảnh đất có kích thước M x N. Tìm số lượng cột đèn ít nhất cần thiết để chiếu sáng toàn bộ mảnh đất. Mỗi ô vuông cần được chiếu sáng ít nhất một lần.

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

Cách Công thức chung cho mọi trường hợp

#include <iostream>
using namespace std;

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

    long long row = (m + 1) / 2;
    long long col = (n + 1) / 2;
    cout << row * col << '\n';
    return 0;
}

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

Đây là cách tiếp cận tối ưu và cũng là cách đơn giản nhất. Ta nhận thấy rằng để tối ưu, các đèn nên được đặt ở vị trí sao cho mỗi đèn chiếu sáng một vùng 2x2 (vì mỗi đèn có thể chiếu 4 ô). Tuy nhiên, nếu M hoặc N là số lẻ, ta không thể chia đều thành các khối 2x2. Giải pháp là đặt các đèn theo ma trận với bước nhảy là 2 ô. Số lượng đèn cần thiết trên mỗi hàng là ceil(N/2) = (N+1)/2. Tương tự cho số hàng, số hàng cần thiết là ceil(M/2) = (M+1)/2. Tổng số đèn là tích của hai số này. Ví dụ: M=2, N=2 -> (2+1)/2 = 1, (2+1)/2 = 1 -> 1 đèn. M=3, N=3 -> (3+1)/2 = 2, (3+1)/2 = 2 -> 4 đèn.

Cách Phương pháp chia cắt theo từng khối 2x2

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

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

    long long ans = (M / 2) * (N / 2);
    if (M % 2 != 0) ans += (N + 1) / 2;
    if (N % 2 != 0) ans += (M + 1) / 2;
    if (M % 2 != 0 && N % 2 != 0) ans -= 1; // Trừ đi ô góc đã đếm 2 lần

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

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

Phương pháp này chia mảnh đất thành các phần:

1. Phần chính giữa là các khối 2x2 hoàn chỉnh, mỗi khối cần 1 đèn.
2. Nếu M lẻ, có một hàng ngang ở dưới cùng (hoặc trên cùng) cần được chiếu. Số đèn cần cho hàng này là ceil(N/2).
3. Nếu N lẻ, có một cột dọc ở bên phải (hoặc trái) cần được chiếu. Số đèn cần cho cột này là ceil(M/2).
4. Nếu cả M và N đều lẻ, ô ở góc dưới cùng bên phải bị đếm 2 lần (một lần bởi hàng ngang, một lần bởi cột dọc), nên cần trừ đi 1. Công thức này về cơ bản là một cách viết khác của (M+1)/2 * (N+1)/2.

Cách Phương pháp kiểm tra chia hết cho 4

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

int main() {
    long long M, N;
    cin >> M >> N;
    if(M*N % 4 == 0) cout << M*N/4;
    else cout << ((M + 1) / 2) * ((N + 1) / 2) << "\n";
    return 0;
}

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

Đây là một phiên bản thử nghiệm (heuristic) dựa trên quan sát rằng nếu diện tích MN chia hết cho 4, ta có thể che phủ hoàn toàn bằng các khối 2x2, cần MN/4 đèn. Tuy nhiên, cách này không chính xác cho tất cả các trường hợp lẻ. Ví dụ, với M=1, N=4, diện tích chia hết cho 4 (1*4/4=1), nhưng ta cần 2 đèn (mỗi đèn chỉ chiếu 1 ô bên trái và 1 ô bên phải, nhưng nếu đặt ở đầu và cuối thì che được 4 ô). Thực tế, công thức chuẩn (M+1)/2 * (N+1)/2 mới là chính xác cho mọi trường hợp. Các solutions mẫu sử dụng code này có thể pass do cách test case hoặc do may mắn, nhưng về mặt toán học thì chưa tối ưu bằng approach 1.

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

Bài học kinh nghiệm

• Mỗi cột đèn có thể chiếu sáng tối đa 4 ô vuông. Do đó, về lý thuyết, ta cần ít nhất (M*N)/4 cột đèn.
• Để đạt được số lượng ít nhất, các cột đèn nên được đặt chéo nhau (dạng ô bàn cờ) với khoảng cách 2 ô theo cả hàng dọc và hàng ngang.
• Công thức tối ưu cho mọi trường hợp là ((M + 1) / 2) * ((N + 1) / 2).

Lỗi thường gặp

• Sử dụng các công thức phức tạp dựa trên phép chia lấy dư (modulo) thay vì công thức đơn giản là làm tròn lên số hàng và số cột.
• Quên xử lý kiểu dữ liệu lớn (long long) khi M và N có thể lên tới 10^6, dẫn đến tràn số nếu dùng int.
• Nhầm lẫn giữa việc chiếu sáng các ô lẻ và việc tối ưu hóa vị trí đặt đèn.