সি++-এ দেয়া কোঅর্ডিনেট থেকে চাএকোয়ার কোঅর্ডিনেটে যাওয়া সম্ভব কিনা চেক করা

মান লযয দুটি কোঅর্ডিনেট (sx, sy), এবং (tx, ty) আছে, আমাদের চেক করতে হবে আমরা কি শুরু বিন্দু থেকে শেষ বিন্দুতে যেতে পারি বা না। এখানে যাওয়া মানে একটি বিন্দু (x, y) নেওয়া এবং সেটিকে হয় (x, x+y) বা (x+y, y)-এ রূপান্তর করা।

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

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• যখন tx > sx এবং ty > sy, করুন:
  • যদি tx > ty, তবে:
    • tx := tx mod ty
  • অন্যথায়:
    • ty := ty mod tx
• ফেরত দিন (true যখন sx একই tx এবং sy <= ty এবং (ty - sy) mod tx ০ এর সমান) OR (sy একই ty এবং x >= sx এবং (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