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

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

যদি ইনপুট হয় coins = [1, 2, 3], salaries = [1, 2], তবে আউটপুট হবে ৪, কারণ: প্রথম কয়েন (মান ১) ব্যবহার না করলে দুটি কয়েনই দুজন কর্মীর জন্য বৈধ, তাই ২ পদ্ধতি। প্রথম কয়েন ব্যবহার করলে সেটি শুধু প্রথম কর্মীর যাবে, বাকি কয়েন যেকোনো একটি দিয়ে দ্বিতীয় কর্মীকে দিতে পারি। মোট ৪ পদ্ধতি।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

coins এবং salaries তালিকাগুলো সাজান।
num_coins := coins-এর আকার, num_salaries := salaries-এর আকার
dp := একটি নতুন ম্যাপ
salaries-এ থাকা প্রতিটি salary-এর জন্য:
- 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, তবে ০ ফেরত দিন
- dp[salary] := idx
res := 1
i কে num_salaries - 1 থেকে ০ পর্যন্ত কমিয়ে যান:
- salary := salaries[i], idx := dp[salary]
- res := res * (num_coins - idx + 1) - (num_salaries - i)
res mod 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]