C++-এ দেওয়া লাইন সেগমেন্ট দিয়ে সর্বোচ্চ সমান্তরালচতুর্ভুজ বানানো

দেওয়া কাজ হল দেওয়া N সংখ্যক লাইন সেগমেন্ট ব্যবহার করে সর্বোচ্চ কতগুলো সমান্তরালচতুর্ভুজ বানানো যায় তা খুঁজে বের করা, যদি প্রতিটি লাইন সেগমেন্ট hoogরতম একটি সমান্তরালচতুর্ভুজে ব্যবহার করা যায়।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট - Arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

আউটপুট - ২

ব্যাখ্যা - উপরের লাইন সেগমেন্ট দিয়ে যেব دوটি সমান্তরালচতুর্ভুজ বানানো যায় সেগুলোর পার্শ্ব হল ৮, ১, ৮, ১ এবং ৩, ৩, ৩, ৩।

ইনপুট - Arr[] = {7, 9, 9, 7}

আউটপুট - ১

প্রোগ্রামে ব্যবহৃত পদ্ধতি

সর্বোচ্চ সমান্তরালচতুর্ভুজের সংখ্যা = ৪টি সমান পার্শ্ব দিয়ে বানানো সমান্তরালচতুর্ভুজ + ২টি সমান পার্শ্ব দিয়ে বানানো সমান্তরালচতুর্ভুজ।
MaxParr() ফাংশনে L = Arr[0] ভেরিয়েবল আরম্ভ করুন যা ফ্রিকোয়েন্সি অ্যারেতে ব্যবহার হবে।
i=1 থেকে i<N পর্যন্ত লুপ চালান এবং চেক করুন if (Arr[i] > L), সত্য হলে L=Arr[i]। লুপের বাইরে L-এ ১ যোগ করুন।
তারপর ফ্রিকোয়েন্সি অ্যারে int Freq[L] = {0} আরম্ভ করুন। i=0 থেকে i<N পর্যন্ত লুপ চালান এবং প্রতিটি সেগমেন্টের ঘটনা ১ করে বাড়ান।
count = 0 ইন্টিজার আরম্ভ করুন ফাইনাল কাউন্ট সংরক্ষণের জন্য।
i=0 থেকে i<L পর্যন্ত লুপ চালান এবং ৪টি সমান পার্শ্ব দিয়ে বানানো সমান্তরালচতুর্ভুজ চেক করুন এবং পাওয়া গেলে count বাড়ান।
left=0 ইন্টিজার আরম্ভ করুন ২টি সমান পার্শ্ব দিয়ে বানানো সমান্তরালচতুর্ভুজের সংখ্যা সংরক্ষণের জন্য।
শেষে i=0 থেকে i<L পর্যন্ত লুপ চালান এবং চেক করুন if(Freq[i] >= 2) সত্য হলে left-এ ১ যোগ করুন।
count += left/2 করুন এবং count ফেরত দিন।

C++ প্রোগ্রাম উদাহরণ

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

int MaxParr(int N, int Arr[]){
    // ফ্রিকোয়েন্সি অ্যারেতে লেথ বের করা
    int L = Arr[0];
    for (int i = 1; i < N; i++){
        if (Arr[i] > L)
            L = Arr[i];
    }
    L = L + 1;
    int Freq[L] = {0};
    for (int i = 0; i < N; i++){
        // প্রতিটি লাইন সেগমেন্টের ঘটনা বাড়ানো
        Freq[Arr[i]] += 1;
    }
    // সমান্তরালচতুর্ভুজের সংখ্যা সংরক্ষণের জন্য
    int count = 0;
    for (int i = 0; i < L; i++){
        /*৪টি সমান পার্শ্ব দিয়ে বানানো সমান্তরালচতুর্ভুজ*/
        count += int(Freq[i] / 4);
        Freq[i] = Freq[i] % 4;
    }
    int left = 0;
    for (int i = 0; i < L; i++){
        // ২ বা অধিক ঘটনা অবশিষ্ট সেগমেন্ট কাউন্ট করা
        if (Freq[i] >= 2)
            left += 1;
    }
    /*২টি সমান পার্শ্ব দিয়ে বানানো সমান্তরালচতুর্ভুজ ফাইনাল কাউন্টে যোগ করা*/
    count += left / 2;
    return count;
}

int main(){
    int N = 10;
    int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
    cout<< MaxParr(N, Arr);
}