पायथन में बेबी और जायंट स्टेप्स द्वारा डेस्टिनेशन तक पहुंचने के लिए इष्टतम चरणों की संख्या ढूंढना

मान लीजिए हमारे पास क्वेरीज की एक लिस्ट Q है, जहां प्रत्येक क्वेरी Q[i] में एक ट्रिपल [a_i, b_i, d_i] होता है। मान लीजिए हम प्रारंभ में पोजीशन (0, 0) पर हैं, फिर एक चरण में हम किसी पोजीशन (x1, y1) से (x2, y2) पर जा सकते हैं जहां इन दो पॉइंट्स के बीच यूक्लिडियन दूरी कम से कम a और अधिकतम b है। अब प्रत्येक क्वेरी के लिए हमें (0, 0) से (d_i, 0) तक पहुंचने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है Q = [(2,3,1), (1,2,0), (3,4,11)], तो आउटपुट होगा [2, 0, 3] क्योंकि पहली क्वेरी के लिए (0, 0) से a = 2 के साथ हम (1/2, sqrt(15)/2) पर जा सकते हैं फिर (1, 0) तो हमें दो चरण चाहिए, आउटपुट 2 है। अगली क्वेरी के लिए d 0 है, तो हमें कोई चरण नहीं चाहिए आउटपुट 0 है। और तीसरे के लिए b = 4 और a = 3 (0, 0) से (4, 0) फिर (8, 0) फिर (11, 0) पर जाएं।

समाधान दृष्टिकोण

न्यूनतम चरण ज्यामिति से प्राप्त होते हैं: यदि d=0 तो 0 चरण। यदि d a या b के बराबर है तो 1 चरण। यदि d < max(a,b) तो 2 चरण (त्रिभुज असमानता)। अन्यथा ceil(d / max(a,b)) चरण।

steps(a, b, d) फंक्शन परिभाषित करें।
mmin = min(a,b), mmax = max(a,b) की गणना करें।
केस संभालें: d==0 -> 0, d in [mmin, mmax] -> 1, d < mmax -> 2, अन्यथा ceil(d/mmax)।
मुख्य फंक्शन में, प्रत्येक क्वेरी के लिए steps लागू करें और परिणाम एकत्र करें।

पायथन कार्यान्वयन

from math import ceil

def steps(a, b, d):
    mmin = min(a, b)
    mmax = max(a, b)
    if d == 0:
        return 0
    if d in [mmin, mmax]:
        return 1
    if d < mmax:
        return 2
    return ceil(d / mmax)

def solve(Q):
    res = []
    for q in Q:
        a, b, d = q
        res.append(steps(a, b, d))
    return res

Q = [(2,3,1), (1,2,0), (3,4,11)]
print(solve(Q))

इनपुट

[(2,3,1), (1,2,0), (3,4,11)]

आउटपुट

[2, 0, 2.0]