C++ প্রোগ্রামে একটি চেনাশোনাতে বাক্সে যোগদান করা সম্ভব কিনা তা পরীক্ষা করার জন্য প্রশ্ন

এই সমস্যায়, আমাদেরকে একটি সংখ্যা n দেওয়া হয়েছে যা একটি বৃত্তের প্রান্তে থাকা n বাক্সগুলিকে বোঝায়। এবং দুটি পূর্ণসংখ্যা, a এবং b নিয়ে গঠিত প্রতিটি প্রশ্ন প্রশ্ন রয়েছে। আমাদের কাজ হল একটি চেনাশোনা বাক্সে যোগদান করা সম্ভব কিনা তা পরীক্ষা করার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা৷

সমস্যা বর্ণনা − প্রতিটি প্রশ্নের সমাধান করার জন্য, আমাদের একটি রড দ্বারা বক্স a ​​এবং বক্স b সংযোগ করার সম্ভাবনা এমনভাবে পরীক্ষা করতে হবে যাতে শেষ ক্যোয়ারী থেকে বক্সগুলির ছেদকে বিরক্ত করা না যায়। আমাদের সম্ভব প্রিন্ট করতে হবে অথবা সম্ভব নয় শর্তের উপর ভিত্তি করে।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}}

আউটপুট

Possible
Not possible
Possible

ব্যাখ্যা

কঠিন লাইন হল রড যা সংযুক্ত করা যায়, যেখানে ড্যাশড লাইন হল সেই লাইন যা সংযোগ করা যায় না।

সমাধান পদ্ধতি

সমস্যার একটি সহজ সমাধান হল প্রতিটি প্রশ্নের জন্য কোয়েরির সমাধান খুঁজে বের করার মাধ্যমে, আমরা প্রদত্ত বক্স বক্স a ​​এবং বক্স b সংযোগ করা যায় কিনা তা খুঁজে বের করব। এর জন্য, আমাদের শেষ ক্যোয়ারির মানগুলিকে রেফারেন্স পয়েন্ট হিসাবে রাখতে হবে এবং তারপরে সংযোগটি সম্ভব কি না তা পরীক্ষা করতে হবে৷

আসুন বাক্সগুলি বিবেচনা করি a এবং b কোয়েরির (i-1) রেফারেন্স রেফারেন্স 1 এবং ref2 হিসাবে। তারপর বিন্দু a এবং b রডের বিপরীত দিকে আছে কিনা তা সন্ধান করুন।

এর জন্য, আমরা দুটি শর্ত পরীক্ষা করব,

শর্ত 1 − যদি (ref1

শর্ত 2 − যদি (ref1

উভয় ক্ষেত্রেই, ফলাফল সম্ভব হবে না।

#include <iostream>
using namespace std;
int printSolutoin(int n, int a, int b, int ref1, int ref2, int lastConn){
   if(lastConn == 0 && a != b)
      return 1;
      int temp;
   if(a > b){
      temp = a;
      a = b;
      b = temp;
   }
   if(ref1 > ref2){
      temp = ref1;
      ref1 = ref2;
      ref2 = temp;
   }
   if( ( ref1 < a && a < b && b < ref2) )
      return 1;
   if( (ref1 <= a <= ref2) && (ref2 <= b <= n) ) return 0;
   else if( (ref1 <= b <= ref2) && (ref2 <= a <= n) )
      return 0;
      return 0;
      return 1;
}
void solveAllQueries(int n, int q, int query[][2]){
   int lastConn = printSolutoin(n, query[0][0], query[0][1], 0, 0, 0);
   lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   for(int i = 1; i < q; i++){
      lastConn = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1],       lastConn);
      lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   }
}
int main() {
   int n = 6;
   int Q = 3;
   int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
   return 0;
}

Possible
Not Possible
Possible