จำนวน 1 สูงสุดในเมทริกซ์ N×N ภายใต้เงื่อนไขใน C++

ภาพรวมปัญหา

หาจำนวน 1 สูงสุดในเมทริกซ์ไบนารี N×N โดยที่ทุกซับเมทริกซ์ X×X ต้องมี 0 อย่างน้อย 1 ตัว (X ≤ N)

ตัวอย่าง

Input: N = 4, X = 2
Output: 12
Matrix:
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Input: N = 7, X = 3
Output: 45

แนวทางแก้ปัญหา

• จำนวน 0 ขั้นต่ำที่ต้องมี = (N / X)² (วาง 0 เป็นกริดห่างกัน X)
• จำนวน 1 สูงสุด = N² - (N / X)²

ตัวอย่างโค้ด C++

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

int MaxOne(int N, int X) {
    int Z = (N / X);
    Z = Z * Z;
    int total = N * N;
    int ans = total - Z;
    return ans;
}

int main() {
    int N = 4, X = 2;
    cout << MaxOne(N, X);
    return 0;
}

ผลลัพธ์

12