দেওয়া কাজ হল একটি দেওয়া ইন্টিজার N দিয়ে একটি ট্রি নির্মাণ করা যাতে, সকল অর্ডার্ড পেয়ার (x,y) এর জন্য degree(x) * degree(y) এর যোগফল সর্বোচ্চ হয় এবং x ≠ y।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট - N=5
আউটপুট - ৫০
ব্যাখ্যা
1
\
2
\
3
\
4
\
5
১ম নোডের ডিগ্রি = ১
২য় নোডের ডিগ্রি = ২
৩য় নোডের ডিগ্রি = ২
৪র্থ নোডের ডিগ্রি = ২
৫ম নোডের ডিগ্রি = ১
সকল অর্ডার্ড পেয়ার (x, y) এর ডিগ্রি গুণফলের যোগফল -
১ম নোড = ১*২ + ১*২ + ১*২ + ১*১ = ৭ ২য় নোড = ২*১ + ২*২ + ২*২ + ২*১ = ১২ ৩য় নোড = ২*১ + ২*২ + ২*২ + ২*১ = ১২ ৪র্থ নোড = ২*১ + ২*২ + ২*২ + ২*১ = ১২ ৫ম নোড = ১*২ + ১*২ + ১*২ + ১*১ = ৭ মোট যোগফল = ৫০
ইনপুট - N=7
আউটপুট - ১২২
প্রোগ্রামে ব্যবহৃত পদ্ধতি
একটি ট্রিতে সকল নোডের ডিগ্রির যোগফল = (2 * N) - 2। এখানে N = ট্রিতে নোডের সংখ্যা। যোগফল সর্বাধিক করতে হলে লিফ নোডের সংখ্যা ন্যূনতম করতে হবে।
Max() ফাংশনে int sum=0 আরম্ভ করুন এবং x=1 এবং y=1 থেকে x<=N এবং y<=N কন্ডিশন সহ নেস্টেড লুপ তৈরি করুন।
নেস্টেড লুপের ভেতরে প্রথমে চেক করুন if(x==y), সত্য হলে continue; স্টেটমেন্ট দিন।
অন্যথায় int degree=2 আরম্ভ করুন এবং if স্টেটমেন্ট দিয়ে চেক করুন if(x==1 || x==n)। সত্য হলে degreeX=1। y-এর জন্যও একইভাবে degreeY নির্ণয় করুন।
শেষে লুপ বন্ধ করার আগে sum ভেরিয়েবল আপডেট করুন - sum += (degreeX * degreeY)।
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int Max(int N){
int sum = 0;
for (int x = 1; x <= N; x++){
for (int y = 1; y <= N; y++){
if (x == y)
continue;
// নোড x-এর ডিগ্রি ২ আপডেট
int degreeX = 2;
// যদি x লিফ নোড বা রুট নোড হয়
if (x == 1 || x == N)
degreeX = 1;
// নোড y-এর ডিগ্রি ২ আপডেট
int degreeY = 2;
// যদি y লিফ নোড বা রুট নোড হয়
if (y == 1 || y == N)
degreeY = 1;
// যোগফল আপডেট
sum += (degreeX * degreeY);
}
}
return sum;
}
// মেইন ফাংশন
int main(){
int N = 5;
cout << Max(N);
}
আউটপুট
50
