मान लीजिए हमारे पास एक प्रारंभिक बिंदु (sx, sy) और एक लक्ष्य बिंदु (tx, ty) है। हमें जांचना है कि क्या प्रारंभिक बिंदु से लक्ष्य बिंदु तक चालों का कोई क्रम मौजूद है। यहां एक चाल में एक बिंदु (x, y) को लेना और उसे या तो (x, x+y) या (x+y, y) में बदलना शामिल है।
उदाहरण के लिए, यदि इनपुट है (sx, sy) = (1,1) और (tx, ty) = (4,5), तो आउटपुट True होगा, क्योंकि चालें हैं: (1,1) से (2,1), फिर (3,1), फिर (4,1), फिर (4,5)।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक फंक्शन solve() परिभाषित करें जो sx, sy, tx, ty लेता है
यदि sx > tx या sy > ty, तो False लौटाएं
यदि sx, tx के बराबर है, तो (ty-sy) % sx == 0 लौटाएं
यदि sy, ty के बराबर है, तो (tx-sx) % sy == 0 लौटाएं
अन्यथा, solve(sx, sy, tx-ty, ty) या solve(sx, sy, tx, ty-tx) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(sx, sy, tx, ty):
if sx > tx or sy > ty:
return False
if sx == tx:
return (ty - sy) % sx == 0
if sy == ty:
return (tx - sx) % sy == 0
return solve(sx, sy, tx - ty, ty) or solve(sx, sy, tx, ty - tx)
(sx, sy) = (1, 1)
(tx, ty) = (4, 5)
print(solve(sx, sy, tx, ty))इनपुट
(1,1), (4,5)
आउटपुट
True
