সমস্যা বিবরণ
N সংখ্যক ছাত্র দেওয়া আছে এবং একটি অ্যারে যা ছাত্রদের প্রাপ্ত নম্বর প্রতিনিধিত্ব করে। স্কুল তাদেরকে পুরস্কার হিসেবে টেডি বেয়ার দিতে চায়। তবে স্কুল টাকা বাঁচাতে চায়, তাই নিচের সীমাবদ্ধতা লাগিয়ে টেডি বেয়ার বিতরণের মোট সংখ্যা ন্যূন করতে চায়:
- সকল ছাত্র কমপক্ষে একটি টেডি পাবে
- যদি দুজন ছাত্র naastে বসে থাকে তবে বেশি নম্বর পাওয়া ছাত্র বেশি টেডি পাবে
- যদি দুজন ছাত্রের নম্বর সমান হয় তবে তারা ভিন্ন সংখ্যক টেডি পেতে পারে
উদাহরণ
মনে করুন ৩ জন ছাত্র আছে এবং তাদের নম্বর অ্যারেতে:
arr[] = {2, 3, 3}
তাহলে বিতরণ করা টেডি: {1, 2, 1} অর্থাৎ মোট ৪ টি টেডি
অ্যালগরিদম
এই সমস্যাটি ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়:
1. N সাইজের একটি টেবিল তৈরি করুন এবং ১ দিয়ে ইনিশিয়ালাইজ করুন (প্রতিটি ছাত্র কমপক্ষে একটা টেডি পাবে)
2. নম্বর অ্যারে 위로 ইটারেট করুন এবং নিচের স্টেপগুলো করুন:
a. যদি বর্তমান ছাত্রের নম্বর পূর্বের ছাত্রের চেয়ে বেশি হয়:
i. পূর্বের ছাত্রকে কত টেডি मिलেছে তা বের করুন
ii. টেডি কাউন্ট ১ বাড়ান
b. যদি বর্তমান ছাত্রের নম্বর কম হয়:
i. আগে এসাইন করা ভ্যালুগুলো রিভিউ এবং চেঞ্জ করুন
উদাহরণ কোড
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int teddieDistribution(int *marks, int n) {
int table[n];
fill(table, table + n, 1);
for (int i = 0; i < n - 1; ++i) {
if (marks[i + 1] > marks[i]) {
table[i + 1] = table[i] + 1;
} else if (marks[i] > marks[i + 1]) {
int temp = i;
while (true) {
if (temp >= 0 && (marks[temp] > marks[temp + 1])) {
if (table[temp] > table[temp + 1]) {
--temp;
continue;
} else {
table[temp] = table[temp + 1] + 1;
--temp;
}
} else {
break;
}
}
}
}
int totalTeddies = 0;
for (int i = 0; i < n; ++i) {
totalTeddies += table[i];
}
return totalTeddies;
}
int main() {
int marks[] = {2, 6, 5, 2, 3, 7};
int totalTeddies = teddieDistribution(marks, SIZE(marks));
cout << "Total teddies to be distributed: " << totalTeddies << "\n";
return 0;
}
আউটপুট
Total teddies to be distributed: 12
