একটি সমস্যা সমাধান করতে হবে যেখানে একটি অ্যারে দেওয়া আছে যেটিতে বক্সগুলোর সাইজ (size) রয়েছে। এখন একটি শর্ত দেওয়া আছে: একটি ছোট বক্স একটি বড় বক্সের ভেতরে রাখা যাবে যদি বড় বক্সটি ছোট বক্সটির কমপক্ষে দুগুণ (twice) বড় হয়। এখন আমাদের বের করতে হবে কতগুলো বক্স দৃশ্যমান (visible) থাকবে। উদাহরণ।
ইনপুট: arr[] = { 1, 3, 4, 5 } আউটপুট: 3 সাইজ ১ এর বক্সটি সাইজ ৩ এর বক্সে রাখা হয়েছে।
ইনপুট: arr[] = { 4, 2, 1, 8 } আউটপুট: 1
এই সমস্যাতেই, আমাদের পদ্ধতি হবে অ্যারেটি সর্ট (sort) করা। এরপর আমরা কিউ (queue) ব্যবহার করব। যেহেতু আমরা এগিয়ে যাচ্ছি, আমরা চেক করব বর্তমান এলিমেন্ট (current element) কি কিউয়ের ফ্রন্ট (front) এলিমেন্টের কমপক্ষে দুগুণ বড়। যদি সত্য হয়, তবে ফ্রন্ট এলিমেন্টটি পপ (pop) করব। অবশেষে বর্তমান এলিমেন্টটি কিউতে পুশ (push) করব। শেষে কিউর সাইজ (size) হব আমাদের উত্তর।
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; // বক্স সাইজের অ্যারে int n = sizeof(arr) / sizeof(arr[0]); // অ্যারে সাইজ queue<int> q; sort(arr, arr + n); // অ্যারে সর্ট q.push(arr[0]); // সবচেয়ে ছোট এলিমেন্ট ফ্রন্টে পুশ for (int i = 1; i < n; i++) { // অ্যারে ট্রাভার্স int curr = q.front(); // ফ্রন্ট এলিমেন্ট if (arr[i] >= 2 * curr) // বর্তমান বক্স ফ্রন্টের দুগুণ বড় হলে q.pop(); // ফ্রন্ট পপ q.push(arr[i]); // বর্তমান এলিমেন্ট পুশ } cout << q.size() << "\n"; // উত্তর return 0; }
3
এই টিউটোরিয়ালে আমরা একটি বক্স অন্য বক্সের ভেতরে রাখার পর দৃশ্যমান বক্সের সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
