Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में उन प्रारंभिक बिंदुओं की संख्या खोजने का प्रोग्राम जहां से हम यात्रा शुरू कर सकते हैं


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

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

  • हम शहर 0 से शुरू कर सकते हैं, टैंक को 3 इकाई ईंधन से भरते हैं, और शहर 1 तक यात्रा करने के लिए 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 := fuel का आकार
  • req := आकार n की एक सरणी जिसे 0 से भरा गया है
  • k को 0 से 1 तक की रेंज में, करें
    • i को n-1 से 0 तक, 1 से घटाते हुए, करें
      • nexti :=(i + 1) mod n
      • req[i] := 0 और req[nexti] + costs[i] - fuel[i] का अधिकतम
      • यदि (req[i] + fuel[i] और cap का न्यूनतम) - costs[i] < req[nexti], तो
        • 0 लौटाएं
  • r में 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

  1. पायथन में पहले से अंतिम नोड तक प्रतिबंधित पथों की संख्या ज्ञात करने का प्रोग्राम पायथन में पहले से अंतिम नोड तक प्रतिबंधित पथों की संख्या ज्ञात करने का प्रोग्राम

    मान लीजिए हमारे पास एक अनिर्देशित भारित संयुक्त ग्राफ है। ग्राफ में n नोड्स हैं और वे 1 से n तक लेबल किए गए हैं। प्रारंभ से अंत तक एक पथ नोड्स के अनुक्रम की तरह है जैसे [z0, z1, z2, ..., zk] यहां z0 प्रारंभ नोड है और zk अंत नोड है और 0 <= i dist(zi+1) जहां 0 <= i <= k-1। इसलिए, हमें नोड 1 से नोड n

  1. - पायथन में अधिकतम सिक्के एकत्र करने का प्रोग्राम

    मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां प्रत्येक सेल कुछ सिक्के संग्रहीत करता है। यदि हम [0,0] से शुरू करते हैं, और केवल दाएं या नीचे जा सकते हैं, तो हमें नीचे-दाएं कोने तक पहुंचने तक एकत्र किए जा सकने वाले अधिकतम सिक्कों की संख्या ढूंढनी है। उदाहरण के लिए, यदि इनपुट है: 1422 6005 तो आउटपुट

  1. - पायथन में उन स्ट्रिंग्स की संख्या खोजें जहां 'a' 'a' या 'b' हो सकता है, और 'b' 'b' ही रहता है

    मान लीजिए हमारे पास केवल a और b वाली एक स्ट्रिंग s है। a a रह सकते हैं या b में बदल सकते हैं, लेकिन b को बदला नहीं जा सकता। हमें उन अद्वितीय स्ट्रिंग्स की संख्या ढूंढनी है जो हम बना सकते हैं। उदाहरण के लिए, यदि इनपुट है s = baab, तो आउटपुट होगा 4, क्योंकि हम ये स्ट्रिंग्स बना सकते हैं: [baab, babb,