पायथन में श्रमिकों को सिक्के वितरित करने के तरीकों की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास सकारात्मक संख्याओं की दो सूचियाँ हैं जिन्हें सिक्के और वेतन कहा जाता है। यहां सिक्के [i] सिक्का I और वेतन के मूल्य को इंगित करता है [j] कार्यकर्ता जे के लिए भुगतान करने के लिए आवश्यक वेतन की कम से कम राशि को इंगित करता है। अब मान लीजिए कि हमारे पास प्रति प्रकार एक सिक्का है और हमें प्रत्येक कार्यकर्ता को ठीक एक सिक्का देना होगा, हमें प्रत्येक कार्यकर्ता को सिक्के देने के तरीकों की संख्या की गणना करनी होगी। यहां दो तरीके अलग हैं यदि कोई कार्यकर्ता एक तरह से एक प्रकार का सिक्का प्राप्त करता है लेकिन दूसरे तरीके से एक अलग प्रकार का सिक्का प्राप्त करता है। यदि परिणाम बहुत बड़ा है तो वापसी परिणाम मॉड 10^9+7।

इसलिए, यदि इनपुट सिक्के =[1, 2, 3], वेतन =[1, 2] की तरह है, तो आउटपुट 4 होगा, जैसे कि हम पहले सिक्के (मान 1) का उपयोग नहीं करते हैं, तो दोनों सिक्के हैं दोनों श्रमिकों के लिए मान्य है, इसलिए श्रमिकों को भुगतान करने के दो तरीके हैं। अब अगर हम पहले सिक्के का उपयोग करते हैं, तो यह केवल पहले कार्यकर्ता के पास जा सकता है, और फिर हम शेष सिक्के में से किसी एक का उपयोग दूसरे कार्यकर्ता को भुगतान करने के लिए कर सकते हैं। तो इसके चार तरीके हैं।

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

• सूची के सिक्कों को क्रमबद्ध करें, और सूची वेतन को क्रमबद्ध करें
• num_coins :=सिक्कों का आकार
• num_salaries :=वेतन का आकार
• dp :=एक नया नक्शा
• वेतन में प्रत्येक वेतन के लिए, करें
  • l :=0, r :=num_coins - 1
  • idx :=num_coins
  • जबकि l <=r, करते हैं
    • एम:=एल +(आर - एल) / 2
    • यदि सिक्के[m]>=वेतन, तो
      • आईडीएक्स:=मी
      • r :=m - 1
    • अन्यथा,
      • एल :=एम + 1
  • यदि idx, num_coins के समान है, तो
    • वापसी 0
  • dp[वेतन] :=idx
• res :=1
• मेरे लिए num_salaries - 1 से 0 की सीमा में, 1 से घटाएं
  • वेतन:=वेतन[i]
  • आईडीएक्स:=डीपी[वेतन]
  • res :=res *(num_coins - idx + 1) -(num_salaries - i)
• रिटर्न रेस मोड 10^9+7

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

उदाहरण

class Solution:
   def solve(self, coins, salaries):
      coins.sort()
      salaries.sort()
      num_coins = len(coins)
      num_salaries = len(salaries)
      dp = {}
      for salary in salaries:
         l = 0
         r = num_coins - 1
         idx = num_coins
         while l <= r:
            m = l + (r - l) // 2
            if coins[m] >= salary:
               idx = m
               r = m - 1
            else:
               l = m + 1
         if idx == num_coins:
            return 0
         dp[salary] = idx
      res = 1
      for i in range(num_salaries - 1, -1, -1):
         salary = salaries[i]
         idx = dp[salary]
         res *= (num_coins - idx + 1) - (num_salaries - i)
      return res % (10**9+7)
ob = Solution()
coins = [1, 2, 3]
salaries = [1, 2]
print(ob.solve(coins, salaries))

इनपुट

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

आउटपुट

4