Số lượng bit 1 tối đa trong ma trận nhị phân N×N với ràng buộc X×X C++

Cho ma trận nhị phân N×N và số X ≤ N. Mọi ma trận con X×X phải chứa ít nhất một số 0. Tìm số lượng bit 1 tối đa có thể đặt.

Ví dụ

N = 4, X = 2 → Output: 12
Ma trận:
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
(Mọi 2x2 đều có 0, tổng 12 bit 1)

N = 7, X = 3 → Output: 45

Quan sát & Công thức

Để thỏa mãn ràng buộc, ta phải đặt số 0 theo lưới đều đặn mỗi X hàng và X cột.

Số ô 0 tối thiểu = ⌊N/X⌋² (đặt 0 tại giao điểm các hàng bội của X và cột bội của X).

Số bit 1 tối đa = N² - ⌊N/X⌋².

Chương trình C++

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

int maxOnes(int N, int X) {
    int zerosPerSide = N / X; // Chia nguyên
    int minZeros = zerosPerSide * zerosPerSide;
    return N * N - minZeros;
}

int main() {
    int N = 4, X = 2;
    cout << maxOnes(N, X); // Output: 12
    return 0;
}

Kết quả

12

Chứng minh ý tưởng

Nếu ít hơn ⌊N/X⌋² số 0, theo nguyên lý Dirichlet, tồn tại một ma trận con X×X không chứa 0 nào. Cách đặt lưới đảm bảo mọi X×X chứa ít nhất một 0 tại giao điểm.