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

पायथन में कितने ट्रांसफर अनुरोध संतुष्ट किए जा सकते हैं यह पता लगाने का प्रोग्राम


मान लीजिए, n संख्या के हॉस्टल कमरे हैं जो 0 से n-1 तक नंबर किए गए हैं। हॉस्टल कमरों के छात्र दूसरे कमरे में ट्रांसफर होना चाहते हैं, और वे ऐसा करने के लिए कई अनुरोध करते हैं। कोई हॉस्टल सीट खाली नहीं रहती, एक ट्रांसफर अनुरोध केवल तभी लिया जाता है जब कोई अन्य छात्र ट्रांसफर करने के इच्छुक छात्र की जगह ले ले। तो, दिए गए अनुरोधों को देखते हुए, हमें यह पता लगाना है कि कितने अनुरोध संतुष्ट किए जा सकते हैं।

उदाहरण के लिए, यदि इनपुट n = 3, requests = [[0,2],[1,0],[2,1]] है, तो आउटपुट 3 होगा।

  • कमरा 0 का छात्र कमरा 2 में ट्रांसफर होता है।
  • कमरा 1 का छात्र कमरा 0 में ट्रांसफर होता है।
  • कमरा 2 का छात्र कमरा 1 में ट्रांसफर होता है।

हल करने के चरण

  1. k को len(requests) से -1 तक घटाते हुए लूप चलाएं:
    • c के लिए range(len(requests)) से k तक सभी कॉम्बिनेशन में लूप चलाएं:
      • d := आकार n का ऐरे जिसमें मान 0 हो
      • c में प्रत्येक i के लिए:
        • d[requests[i][0]] := d[requests[i][0]] - 1
        • d[requests[i][1]] := d[requests[i][1]] + 1
      • यदि d में कोई भी आइटम True नहीं है, तो k वापस करें।
  2. 0 वापस करें।

उदाहरण

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

from itertools import combinations
def solve(n, requests):
    for k in range(len(requests), 0, -1):
        for c in combinations(range(len(requests)), k):
            d = [0] * n
            for i in c:
                d[requests[i][0]] -= 1
                d[requests[i][1]] += 1
            if not any(d):
                return k
    return 0

print(solve(3, [[0,2],[1,0],[2,1]]))

इनपुट

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

आउटपुट

3
  1. Python में कितने क्यूब कटे हैं, यह खोजने का प्रोग्राम Python में कितने क्यूब कटे हैं, यह खोजने का प्रोग्राम

    मान लीजिए, a, b, और c आयामों के कई क्यूब्स हैं, और उनका उपयोग करके axbxc आयाम का एक नया बॉक्स बनाया जाता है। a, b, और c pairwise को-प्राइम हैं; gcd(a, b) = gcd(b,c) = gcd(c, a) = 1। हमें एक सिंगल स्लाइस के साथ बॉक्स को दो टुकड़ों में काटना है जैसा कि चित्र में दिखाया गया है। हमें यह पता करना है कि य

  1. Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक N x N बाइनरी मैट्रिक्स है जहां 0 खाली सेल के लिए है और 1 ब्लॉक्ड सेल है, हमें N खाली सेल चुनने के तरीकों की संख्या ढूंढनी है ताकि हर पंक्ति और हर कॉलम में कम से कम एक चुना हुआ सेल हो। यदि उत्तर बहुत बड़ा है तो परिणाम mod 10^9 + 7 लौटाएंइसलिए, यदि इनपुट इस तरह है000000010तो आउट

  1. पायथन में हम कितना कुल वर्षा जल पकड़ सकते हैं यह खोजने का प्रोग्राम पायथन में हम कितना कुल वर्षा जल पकड़ सकते हैं यह खोजने का प्रोग्राम

    मान लीजिए हमारे पास n गैर-ऋणात्मक पूर्णांकों की एक सरणी है। ये एक ऊंचाई को दर्शा रहे हैं जहां प्रत्येक बार की चौड़ाई 1 है, हमें गणना करनी है कि बारिश के बाद यह कितना पानी पकड़ सकता है। तो मानचित्र इस तरह होगा −यहां हम 8 नीले बॉक्स देख सकते हैं, इसलिए आउटपुट 8 होगा।इसे हल करने के लिए, हम इन चरण