Hiểu bài toán

Bài toán yêu cầu tính số cách tô một bảng m × n bằng hai màu (đen, trắng) sao cho:

1. Có đúng k ô màu đen.
2. Hai ô cùng chung một cạnh không được cùng màu.

Điều kiện 2 là điều kiện của một bàn cờ vua (tô màu xen kẽ). Bất kỳ cách tô đúng điều kiện 2 đều có thể được tạo ra bằng cách chọn 1 trong 2 màu cho ô (1,1) và sau đó các ô còn lại được xác định hoàn toàn (màu của ô (i, j) sẽ bằng màu của (1,1) nếu i+j chẵn, và khác nếu i+j lẻ).

Vì vậy, có tối đa 2 cách tô thỏa mãn điều kiện 2 (tương ứng với ô (1,1) là đen hoặc trắng). Tuy nhiên, nếu t tổng số ô là số lẻ, thì hai cách tô này sẽ có số lượng ô đen khác nhau (một cách có ceil(total/2) ô đen, cách kia có floor(total/2) ô đen). Nếu tổng số ô là số chẵn, cả hai cách đều có total/2 ô đen.

Bài toán quy về kiểm tra xem k có bằng số ô đen của một trong các cách tô hợp lệ hay không.

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

Cách Phân tích Ma trận (Grid Analysis)

#include <iostream>
using namespace std;

int main() {
    long long m, n, k;
    cin >> m >> n >> k;
    long long total = m * n;

    if (total % 2 != 0) {
        // Ma trận có số ô lẻ
        // Hai cách tô sẽ có số ô đen khác nhau: (total + 1) / 2 và total / 2
        if (k == (total + 1) / 2 || k == total / 2) {
            cout << 1;
        } else {
            cout << 0;
        }
    } else {
        // Ma trận có số ô chẵn
        // Cả hai cách tô đều có total / 2 ô đen
        if (k == total / 2) {
            cout << 2;
        } else {
            cout << 0;
        }
    }
    return 0;
}

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

Cách tiếp cận này dựa trên quan sát rằng một bảng được tô màu đúng quy tắc 'không ô chung cạnh cùng màu' là một bàn cờ vua.

• Nếu tổng số ô total = m * n là số lẻ, thì hai cách tô tương ứng với 'ô (1,1) đen' và 'ô (1,1) trắng' sẽ cho số lượng ô đen khác nhau. Cụ thể, một cách có (total + 1) / 2 ô đen, cách còn lại có total / 2 ô đen. Do đó, nếu k bằng 1 trong 2 giá trị này, đáp án là 1 (vì chỉ có 1 cách tô phù hợp với k đó). Nếu không, đáp án là 0.
• Nếu total là số chẵn, cả hai cách tô đều có chính xác total / 2 ô đen. Do đó, nếu k == total / 2, đáp án là 2 (cả hai cách đều hợp lệ). Nếu không, đáp án là 0.
• Mã nguồn của dvhcoder là minh chứng cho cách này.

Cách Tính Toán Số Lượng Ô Đen Theo Kiểu Chẵn/Lẻ (Formulaic Approach)

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

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

    // Tính số ô đen theo kiểu 1 (ô (1,1) là ô có số lượng nhiều hơn nếu t tổng lẻ)
    // Số hàng chẵn và lẻ
    long long rows_odd = (m + 1) / 2;
    long long rows_even = m / 2;

    // Trong một hàng, số ô có cùng màu với ô đầu tiên (tọa độ chẵn) nhiều hơn hoặc bằng
    long long cols_odd = (n + 1) / 2;
    long long cols_even = n / 2;

    // Số ô đen kiểu 1: các ô (i, j) với i+j chẵn
    long long c1 = rows_odd * cols_odd + rows_even * cols_even;

    // Số ô đen kiểu 2: các ô (i, j) với i+j lẻ
    // Số này bằng tổng số ô trừ đi c1
    long long c2 = (m * n) - c1;

    int ans = 0;
    if (c1 == k) ans++;
    if (c2 == k) ans++;

    cout << ans;
    return 0;
}

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

Cách này tính trực tiếp số ô thuộc mỗi nhóm (các ô có tổng tọa độ chẵn và lẻ).

• c1 là số ô (i, j) sao cho i+j là số chẵn.
• c2 là số ô (i, j) sao cho i+j là số lẻ.
• c1 được tính bằng cách nhân số hàng có chỉ số lẻ (vì i bắt đầu từ 1) với số cột có chỉ số lẻ, cộng với số hàng chẵn nhân số cột chẵn.
• c2 bằng total - c1.
• Nếu k bằng c1, có 1 cách tô (ô (1,1) cùng màu với các ô trong nhóm c1).
• Nếu k bằng c2, có 1 cách tô (ô (1,1) cùng màu với các ô trong nhóm c2).
• Nếu k bằng cả hai (chỉ xảy ra khi c1 == c2), đáp án là 2.
• Mã nguồn của dainghiajustiin thể hiện chính xác phương pháp này.

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

Bài học kinh nghiệm

• Bài toán này chỉ là bài toán đếm số cách tô màu trên bàn cờ vua (Checkerboard) sao cho số ô đen bằng k.
• Nếu t tổng số ô là số lẻ, hai cách tô sẽ cho số ô đen khác nhau (khác nhau 1 đơn vị). Nếu t tổng số ô chẵn, hai cách tô cho số ô đen như nhau.
• Vì các ô còn lại được xác định hoàn toàn bởi màu của ô (1,1), nên chỉ có tối đa 2 cách tô hợp lệ về mặt cấu trúc.

Lỗi thường gặp

• Sử dụng int cho m, n và k. Với m, n lên tới 10^9, m * n có thể lên tới 10^18. int (32-bit) chỉ chứa được khoảng 2*10^9. Phải dùng long long (64-bit).
• Tính toán sai công thức chia đôi cho các số lẻ (ví dụ tính sai số lượng ô chẵn/lẻ trong một chiều). Phải dùng (n + 1) / 2 cho số lượng phần tử có chỉ số lẻ (từ 1) và n / 2 cho chỉ số chẵn.
• Quên xử lý trường hợp k quá lớn hoặc âm (dù đề bài cho 0 <= k <= 10^18, nhưng logic phải xử lý đúng nếu k không khớp c1 hay c2).