ภารกิจคือการค้นหาจำนวนสูงสุดของเมทริกซ์ไบนารีที่เป็นไปได้โดยมีข้อจำกัดดังต่อไปนี้
จำนวนเต็มสองจำนวน N และ X ถูกกำหนดโดยที่ X<=N ขนาดของเมทริกซ์ไบนารีควรเป็น N*N และทุกเมทริกซ์ย่อยที่มีขนาด X*X ควรมีอย่างน้อยหนึ่งศูนย์
มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่างกัน −
ป้อนข้อมูล − N=4, X=2
ผลผลิต − 12
คำอธิบาย − เมทริกซ์ผลลัพธ์จะเป็น -
1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1
ป้อนข้อมูล − N=7, X=3
ผลผลิต − 45
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
เพื่อให้ได้จำนวนสูงสุด ขั้นแรกเราต้องค้นหาจำนวนศูนย์ขั้นต่ำที่จำเป็นในเมทริกซ์ที่กำหนด
เมื่อสังเกตรูปแบบทั่วไปในเมทริกซ์ทั้งหมด จะเห็นว่าจำนวนศูนย์ที่ต้องการ =(N / X) 2
ดังนั้นจำนวนสูงสุด =องค์ประกอบทั้งหมดในเมทริกซ์ – จำนวนศูนย์\
-
ในฟังก์ชัน MaxOne() ให้สร้างตัวแปร Z ประเภท int และเก็บค่าศูนย์ขั้นต่ำที่ต้องการซึ่งเท่ากับ (N / X) 2
-
จากนั้นเริ่มต้นตัวแปรอื่น Total =N*N ของประเภท int เพื่อเก็บขนาดรวมของเมทริกซ์
-
จากนั้นให้เริ่มต้น int ans =total – Z เพื่อเก็บคำตอบสุดท้ายและส่งกลับ ans
ตัวอย่าง
#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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
12
