पायथन में फिनिश लाइन तक पहुंचने के लिए चालों की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए, हमारे पास एक कार है और हम इसे एक-आयामी सड़क पर चला रहे हैं। वर्तमान में हम स्थिति = 0 पर हैं और गति = 1 के साथ। हम इन दो ऑपरेशनों में से कोई भी कर सकते हैं।

• त्वरण: स्थिति := स्थिति + गति और गति := गति * 2 रिवर्स गियर: गति := -1 जब गति > 0 अन्यथा गति := 1।

हमें लक्ष्य तक पहुंचने के लिए आवश्यक न्यूनतम चालों की संख्या ज्ञात करनी है।

इसलिए, यदि इनपुट लक्ष्य = 10 है, तो आउटपुट 7 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• dfs() नामक एक फ़ंक्शन परिभाषित करें। यह digit, cost, pos, neg, target लेगा

  • tot := cost + अधिकतम 2*(pos - 1) और 2*(neg - 1)

  • यदि tot >= ans, तो:

    • वापस करें

  • यदि target 0 के समान है, तो:

    • ans := ans और tot का न्यूनतम

    • वापस करें

  • step := (2^digit) - 1

  • यदि step * 2 < |target|, तो:

    • वापस करें

  • dfs(digit - 1, cost, pos, neg, target)

  • dfs(digit - 1, cost + digit, pos + 1, neg, target - step)

  • dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)

  • dfs(digit - 1, cost + digit, pos, neg + 1, target + step)

  • dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)

• मुख्य फ़ंक्शन से, निम्नलिखित करें:

• ans := अनंत

• hi := 1

• जब तक 2^hi < target, करें:

  • hi := hi + 1

• dfs(hi, 0, 0, 0, target)

• ans वापस करें

उदाहरण

class Solution:
    def solve(self, target):
        self.ans = int(1e9)
        hi = 1
        while (1 << hi) < target:
            hi += 1
        self.dfs(hi, 0, 0, 0, target)
        return self.ans
    def dfs(self, digit, cost, pos, neg, target):
        tot = cost + max(2 * (pos - 1), 2 * neg - 1)
        if tot >= self.ans:
            return
        if target == 0:
            self.ans = min(self.ans, tot)
            return
        step = (1 << digit) - 1
        if step * 2 < abs(target):
            return
        self.dfs(digit - 1, cost, pos, neg, target)
        self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
        self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
        self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
        self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)

ob = Solution()
print(ob.solve(10))

इनपुट

10

आउटपुट

7