शुरुआती बिंदु की संख्या खोजने के लिए कार्यक्रम जहां से हम पायथन में यात्रा शुरू कर सकते हैं

मान लीजिए कि n शहर 0 से n-1 तक गिने गए हैं और n निर्देशित सड़कें हैं। हम शहर I से शहर (i + 1)% n [0 से 1 से 2 से .... से N - 1 से 0] तक यात्रा कर सकते हैं। हमारे पास एक कार है। हमारी कार के फ्यूल टैंक की कैपेसिटी कैप यूनिट है। वहाँ ईंधन [i] इकाइयाँ हैं जिनका उपयोग हम शहर i की शुरुआत में कर सकते हैं और कार लागत [i] शहर i से (i + 1)% n तक यात्रा करने के लिए ईंधन की इकाइयाँ लेती है। हमें यह पता लगाना होगा कि ऐसे कितने शहर हैं जहां से हम अपनी कार शुरू कर सकते हैं, ताकि हम सभी शहरों में घूम सकें और उसी शहर तक पहुंच सकें जहां से शुरू हुआ था?

इसलिए, यदि इनपुट कैप =3 ईंधन =[3,1,2] लागत =[2,2,2] जैसा है, तो आउटपुट 2 होगा क्योंकि दो संभावित समाधान हैं।

• हम शहर 0 से शुरू कर सकते हैं, टैंक को 3 यूनिट ईंधन से भर सकते हैं, और शहर की यात्रा के लिए 2 यूनिट ईंधन का उपयोग कर सकते हैं। टैंक में एक इकाई शेष है। शहर 1 में 1 यूनिट ईंधन लेने के बाद, कार में 2 यूनिट ईंधन होता है और हम 2 यूनिट ईंधन का उपयोग करके शहर 2 की यात्रा कर सकते हैं। ईंधन टैंक अब खाली है। शहर 2 में 2 गैलन ईंधन भरने के बाद, हम 2 गैलन ईंधन का उपयोग करके वापस शहर 0 की यात्रा करते हैं।

• हम शहर 2 से शुरू कर सकते हैं, कार को 2 यूनिट ईंधन से भर सकते हैं, और शहर 0 की यात्रा कर सकते हैं। फिर शहर 0 से 3 गैलन ईंधन भरने के बाद, हम शहर 1 की यात्रा करते हैं, और हमारे पास 1 यूनिट ईंधन है। फिर हम सिटी 1 में 1 यूनिट ईंधन भर सकते हैं और अब 2 यूनिट ईंधन और 2 शहर की यात्रा कर सकते हैं।

हालांकि, हम 1 शहर से शुरू नहीं कर सकते हैं, केवल 1 यूनिट ईंधन मौजूद है, लेकिन शहर 2 की यात्रा के लिए 2 गैलन की आवश्यकता होती है।

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

• n :=ईंधन का आकार
• req :=आकार n की एक सरणी और 0 से भरें
• के लिए 0 से 1 की सीमा में, करो
  • n-1 से 0 की श्रेणी में i के लिए, 1 से घटाएं
    • अगला :=(i + 1) मॉड एन
    • req[i] :=अधिकतम 0 और req[nexti] + लागत[i] - ईंधन[i]
    • यदि न्यूनतम (req[i] + ईंधन[i] और कैप) - लागत[i]
    • वापसी 0

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(cap, fuel, costs):
   n = len(fuel)
   req = [0] * n

   for k in range(2):
      for i in range(n-1, -1, -1):
         nexti = (i + 1) % n
         req[i] = max(0, req[nexti] + costs[i] - fuel[i])
         if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
            return 0
   return sum(1 for r in req if r == 0)

cap = 3
fuel = [3,1,2]
costs = [2,2,2]
print(solve(cap, fuel, costs))

इनपुट

3, [3,1,2], [2,2,2]

आउटपुट

2