দেওয়া কাজ হল নিচের বাধাবদ্ধতাগুলো মেনে একটি বাইনারি ম্যাট্রিক্সে সর্বোচ্চ কতগুলো ১ থাকতে পারে তা খুঁজে বের করা।
দুটি ইন্টিজার N এবং X দেওয়া আছে যেখানে X<=N। বাইনারি ম্যাট্রিক্সের আকার হবে N*N এবং X*X আকারের প্রতিটি সাব-ম্যাট্রিক্সে কমপক্ষে একটি শূন্য থাকতে হবে।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট - N=4, X=2
আউটপুট - ১২
ব্যাখ্যা - ফলাফল ম্যাট্রিক্স হবে -
1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1
ইনপুট - N=7, X=3
আউটপুট - ৪৫
প্রোগ্রামে ব্যবহৃত পদ্ধতি
সর্বোচ্চ ১ পেতে হলে প্রথমে ম্যাট্রিক্সে প্রয়োজনীয় ন্যূনতম শূন্যের সংখ্যা বের করতে হবে।
সকল ম্যাট্রিক্সে একটি সাধারণ প্যাটার্ন পর্যবেক্ষণ করলে দেখা যায় যে, প্রয়োজনীয় শূন্যের সংখ্যা = (N / X)²
তাই সর্বোচ্চ ১-এর সংখ্যা = ম্যাট্রিক্সে মোট উপাদান - শূন্যের সংখ্যা
MaxOne() ফাংশনে Z নামক একটি ইন্টিজার ভেরিয়েবল তৈরি করুন এবং তাতে প্রয়োজনীয় ন্যূনতম শূন্যের সংখ্যা সংরক্ষণ করুন যা (N / X)²।
তারপর total = N*N ইন্টিজার ভেরিয়েবল আরম্ভ করুন ম্যাট্রিক্সের মোট আকার সংরক্ষণের জন্য।
শেষে int ans = total - Z আরম্ভ করুন ফাইনাল আউটপুট সংরক্ষণের জন্য এবং ans ফেরত দিন।
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;
int X = 2;
cout << MaxOne(N, X);
return 0;
}
আউটপুট
12
