আমরা পাইথনে কর্মীদের কয়েন বিতরণ করতে পারি তার সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে মুদ্রা এবং বেতন নামে ধনাত্মক সংখ্যার দুটি তালিকা রয়েছে। এখানে কয়েন[i] কয়েন i-এর মান নির্দেশ করে এবং বেতন[j] নির্দেশ করে যে কর্মী j-এর জন্য সর্বনিম্ন পরিমাণ বেতন দিতে হবে। এখন ধরুন আমাদের প্রতি টাইপের একটি কয়েন আছে এবং আমাদের অবশ্যই প্রতিটি শ্রমিককে একটি করে কয়েন দিতে হবে, আমাদের প্রতিটি শ্রমিককে কয়েন দেওয়ার উপায়গুলি গণনা করতে হবে। এখানে দুটি উপায় ভিন্ন যদি কিছু কর্মী এক প্রকারের মুদ্রা এক উপায়ে গ্রহণ করে কিন্তু অন্য উপায়ে ভিন্ন ধরনের মুদ্রা পায়। ফলাফল খুব বড় হলে রিটার্ন রেজাল্ট মোড 10^9+7।

সুতরাং, যদি ইনপুট হয় কয়েন =[1, 2, 3], বেতন =[1, 2], তাহলে আউটপুট হবে 4, যেমন আমরা প্রথম মুদ্রা (মান 1) ব্যবহার না করি, তাহলে উভয় কয়েন উভয় কর্মীদের জন্য বৈধ, তাই শ্রমিকদের অর্থ প্রদানের দুটি উপায় রয়েছে। এখন যদি আমরা প্রথম কয়েনটি ব্যবহার করি, তবে এটি শুধুমাত্র প্রথম শ্রমিকের কাছে যেতে পারে, এবং তারপরে আমরা দ্বিতীয় কর্মীকে অর্থ প্রদানের জন্য অবশিষ্ট মুদ্রার যেকোনো একটি ব্যবহার করতে পারি। তাই চারটি উপায় আছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

তালিকা কয়েন বাছাই করুন, এবং তালিকার বেতন বাছাই করুন
সংখ্যা_কয়েন :=মুদ্রার আকার
সংখ্যা_বেতন :=বেতনের আকার
dp :=একটি নতুন মানচিত্র
বেতনের প্রতিটি বেতনের জন্য, করুন
- l :=0, r :=num_coins - 1
- idx :=num_coins
- যখন l <=r, do
  - m :=l +(r - l) / 2
  - যদি কয়েন[m]>=বেতন, তাহলে
    - idx :=m
    - r :=m - 1
  - অন্যথায়,
    - l :=m + 1
- যদি idx num_coins এর মত হয়, তাহলে
  - রিটার্ন 0
- dp[বেতন] :=idx
res :=1
আমার জন্য রেঞ্জের সংখ্যা_বেতন - 1 থেকে 0, 1 দ্বারা হ্রাস করুন, করুন
- বেতন :=বেতন[i]
- idx :=dp[বেতন]
- 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]