Số lượng ma trận tối đa trong ma trận N * N với các ràng buộc đã cho trong C ++

Nhiệm vụ được giao là tìm số lượng lớn nhất có thể có trong ma trận nhị phân với các ràng buộc sau.

Hai số nguyên N và X được cho trong đó X <=N. Kích thước của ma trận nhị phân phải là N * N và mọi ma trận con có kích thước X * X phải chứa ít nhất một số không.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - N =4, X =2

Đầu ra - 12

Giải thích - Ma trận kết quả sẽ là -

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Đầu vào - N =7, X =3

Đầu ra - 45

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Để có được số lượng lớn nhất, trước tiên chúng ta sẽ phải tìm số lượng số không tối thiểu cần thiết trong ma trận đã cho.

  Bằng cách quan sát một mẫu chung trong tất cả các ma trận, có thể thấy rằng số lượng các số 0 được yêu cầu =(N / X) ²

  Vì vậy, số phần tử tối đa =Tổng số phần tử trong ma trận - số lượng số không \

• Trong hàm MaxOne (), hãy tạo một biến Z kiểu int và lưu trữ trong đó số lượng số 0 tối thiểu được yêu cầu bằng (N / X) ²

• Sau đó, khởi tạo một biến khác total =N * N kiểu int để lưu trữ tổng kích thước của ma trận.

• Sau đó, cuối cùng khởi tạo int ans =total - Z để lưu trữ câu trả lời cuối cùng và trả về ans.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int MaxOne(int N, int X){
   // Minimum number of zeroes that are needed
   int Z = (N / X);
   Z = Z * Z;
   /* Totol elements in matrix = square of the size of the matrices*/
   int total =N * N;
   //Final answer
   int ans = total - Z;
   return ans;
}
int main(){
   int N = 4;
   int X = 2;
   cout << MaxOne(N, X);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

12