পাইথনে রিপিটিং ইন্টিজার বিতরণ করার প্রোগ্রাম

আমাদের একটি অ্যারে nums আছে, এতে সর্বোচ্চ ৫০টি ইউনিক মান থাকে। আমাদের আরেকটি অ্যারে আছে quantity, যেখানে quantity[i] নির্দেশ করে i-তম কাস্টমার কতটুকু মান অর্ডার করেছে। আমাদের যাচাই করতে হবে যে কি nums-কে বিতরণ করা সম্ভব যাতে:

• i-তম কাস্টমারকে ঠিক quantity[i] আইটেম मिलে,

• i-তম কাস্টমার যেসব মান পাবে সেগুলো সব সমান, এবং

• সব কাস্টমার সন্তুষ্ট থাকে।

উদাহরণস্বরূপ, ইনপুট nums = [5,1,2,2,3,4,4,3,3], quantity = [2,2,3] হলে আউটপুট হবে True কারণ দুজন কাস্টমার ২টি করে উপাদান চায়, তারা [2,2] এবং [4,4] পেতে পারে, এবং তৃতীয় কাস্টমার ৩টি চায়, সে [3,3,3] পাবে, তাই সবাই সন্তুষ্ট।

সমাধানের ধাপসমূহ (ব্যাকট্র্যাকিং + ফ্রিকোয়েন্সি কাউন্ট)

• util(i, cntr) ফাংশন ডিফাইন করুন:

  • যদি i == len(quantity) হয়, তবে True রিটার্ন করুন

  • temp_counter := cntr.copy()

  • cntr-এর প্রতিটি cnt এর জন্য:

    • যদি cnt >= quantity[i] হয়, তবে:

      • temp_counter[cnt] -= 1

      • যদি temp_counter[cnt] == 0 হয়, তবে cnt-কে temp_counter-এ থেকে মুছে দিন

      • rem := cnt - quantity[i]

      • temp_counter[rem] += 1

      • যদি util(i+1, temp_counter) true হয়, তবে True রিটার্ন করুন

      • temp_counter[rem] -= 1

      • যদি temp_counter[rem] == 0 হয়, তবে rem-কে মুছে দিন

    • temp_counter[cnt] += 1

  • False রিটার্ন করুন

• মূল মেথড থেকে:

• cnt := nums-এ উপস্থিত সব সংখ্যার ফ্রিকোয়েন্সির ফ্রিকোয়েন্সি ম্যাপ

• quantity-কে রিভার্স সর্ট করুন

• util(0, cnt) রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

from collections import Counter
def solve(nums, quantity):
    def util(i, cntr):
        if i == len(quantity):
            return True
        temp_counter = cntr.copy()
        for cnt in cntr:
            if cnt >= quantity[i]:
                temp_counter[cnt] -= 1
                if temp_counter[cnt] == 0:
                    temp_counter.pop(cnt)
                rem = cnt - quantity[i]
                temp_counter[rem] += 1
                if util(i+1, temp_counter):
                    return True
                temp_counter[rem] -= 1
                if temp_counter[rem] == 0:
                    temp_counter.pop(rem)
            temp_counter[cnt] += 1
        return False
    cnt = Counter(Counter(nums).values())
    quantity.sort(reverse=True)
    return util(0, cnt)

nums = [5,1,2,2,3,4,4,3,3]
quantity = [2,2,3]
print(solve(nums, quantity))

ইনপুট

[5,1,2,2,3,4,4,3,3], [2,2,3]

আউটপুট

True