C++-এ a, b, c দৈর্ঘ্যের লাইন সেগমেন্টের সর্বোচ্চ সংখ্যা

দেওয়া কাজ হল দেওয়া পজিটিভ ইন্টিজার N থেকে a, b এবং c দৈর্ঘ্যের লাইন সেগমেন্টের সর্বোচ্চ সংখ্যা বের করা।

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

ইনপুট - N=8, a=3, b=1, c=2

আউটপুট - ৮

ব্যাখ্যা - N কে b-এর ৮টি সেগমেন্টে ভাগ করা যায় যা সর্বোচ্চ সেগমেন্ট সংখ্যা।

ইনপুট - N=13, a=2, b=7, c=3

আউটপুট - ৬

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

MaxSegment() ফাংশনে MaxSeg[N + 1] নামক একটি ইন্টিজার অ্যারে ডিক্লেয়ার করুন এবং -1 দিয়ে আরম্ভ করুন।
শূন্য-থ ইনডেক্স ০ সেট করুন কারণ এতে কোনো সেগমেন্ট থাকবে না।
i=0 থেকে i<N পর্যন্ত লুপ চালান এবং চেক করুন if (MaxSeg[i] != -1)।
উপরোক্ত if স্টেটমেন্টের ভেতরে আরেকটি if স্টেটমেন্ট রাখুন if(i + a <= N) এবং MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]); সেট করুন।
b এবং c-এর জন্যও একই ধাপ दुहरান।
লুপের বাইরে MaxSeg[N] ফেরত দিন।

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

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

int MaxSegment(int N, int a, int b, int c){
    /* এটি প্রতিটি ইনডেক্সের সর্বোচ্চ সেগমেন্ট সংখ্যা সংরক্ষণ করবে*/
    int MaxSeg[N + 1];
    // আরম্ভিশন
    memset(MaxSeg, -1, sizeof(MaxSeg));
    // ০-থ ইনডেক্সে ০ সেগমেন্ট থাকবে
    MaxSeg[0] = 0;
    // N পর্যন্ত প্রতিটি সেগমেন্টের জন্য ট্রাভার্স
    for (int i = 0; i < N; i++){
        if (MaxSeg[i] != -1){
            if(i + a <= N ){
                MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
            }
            if(i + b <= N ){
                MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
            }
            if(i + c <= N ){
                MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
            }
        }
    }
    return MaxSeg[N];
}

int main(){
    int N = 13, a = 2, b = 7, c = 3;
    cout << MaxSegment(N, a, b, c);
    return 0;
}