C++ এ প্রদত্ত স্থানাঙ্ক থেকে পছন্দসই স্থানাঙ্কে সরানো সম্ভব কিনা তা পরীক্ষা করুন

ধরুন আমাদের দুটি স্থানাঙ্ক (sx, sy), এবং (tx, ty), আমাদের পরীক্ষা করতে হবে যে আমরা শুরু বিন্দু থেকে শেষ বিন্দুতে যেতে পারি কি না। এখানে আমরা একটি বিন্দু (x, y) নিয়ে এটিকে (x, x+y) বা (x+y, y) তে রূপান্তরিত করতে পারি।

সুতরাং যদি ইনপুটগুলি (1, 1) এবং (4,5) হয়, তবে উত্তরটি সত্য হবে, এর কারণ হল (1,1) থেকে (2,1), তারপর (3,1), তারপর (4) ,1), তারপর (4,5)।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যখন tx> sx এবং ty> sy, −
  করুন
  • যদি tx> ty হয়, তাহলে −
    • tx :=tx mod ty
  • অন্যথায়
    • ty :=ty mod tx
• রিটার্ন (সত্য যখন sx tx এবং sy এর মত হয় <=ty AND (ty - sy) mod tx 0 এর মত হয়) বা (sy ty AND x>=sx AND (tx - sx) mod ty হল 0)

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
bool solve(int sx, int sy, int tx, int ty) {
   while(tx > sx && ty > sy){
      if(tx > ty){
         tx %= ty;
      }else ty %= tx;
   }
   return (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
}
main(){
   cout << solve(1,1,4,5);
}

ইনপুট

1, 1, 4, 5

আউটপুট

1