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

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

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

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

सूची coins को सॉर्ट करें, और सूची salaries को सॉर्ट करें
num_coins := coins का आकार
num_salaries := salaries का आकार
dp := एक नया मैप
प्रत्येक salary के लिए salaries में, करें
- l := 0, r := num_coins - 1
- idx := num_coins
- जब तक l <= r, करें
  - m := l +(r - l) / 2
  - यदि coins[m] >= salary, तो
    - idx := m
    - r := m - 1
  - अन्यथा,
    - l := m + 1
- यदि idx, num_coins के समान है, तो
  - 0 वापस करें
- dp[salary] := idx
res := 1
i के लिए num_salaries - 1 से 0 तक, 1 से घटाते हुए, करें
- salary := salaries[i]
- idx := dp[salary]
- res := res *(num_coins - idx + 1) -(num_salaries - i)
res मॉड 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]