পাইথনে স্বতন্ত্র ধরনের আইটেম সহ সর্বাধিক সংখ্যক কে-আকারের গ্রুপ খুঁজে বের করার প্রোগ্রাম সম্ভব

ধরুন আমাদের কাছে গণনা নামে একটি সংখ্যার তালিকা রয়েছে যেখানে গণনা [i] আইটেমের সংখ্যাকে প্রতিনিধিত্ব করে। আমাদের আরও একটি মান k আছে। আমাদের k আকারের সর্বাধিক সংখ্যক গ্রুপ খুঁজে বের করতে হবে, যেমন প্রতিটি গ্রুপে অবশ্যই আলাদা ধরনের আইটেম থাকতে হবে।

সুতরাং, যদি ইনপুটটি গণনা =[2, 3, 5, 3] k =2 এর মত হয়, তাহলে আউটপুট হবে 6, কারণ চার ধরনের আইটেম যথাক্রমে a, b, c, d দ্বারা উপস্থাপন করা হয়। আমাদের k =2 এর নিম্নলিখিত গ্রুপ থাকতে পারে, যেখানে সমস্ত উপাদান আলাদা ধরণের:[(c, a), (b, a), (c, b), (c, b), (d, a), (d, a)]।

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

সম্ভাব্য একটি ফাংশন সংজ্ঞায়িত করুন()। এটি গণনা, গোষ্ঠী, k
প্রয়োজনীয় :=গ্রুপ * k
আমি পরিসীমা 0 থেকে গণনার আকারের জন্য, কর
- temp :=সর্বনিম্ন গণনা[i], গ্রুপ এবং প্রয়োজনীয়
- প্রয়োজনীয় :=প্রয়োজনীয় - টেম্প
- যদি প্রয়োজন হয় 0 এর মতো, তাহলে
  - সত্য ফেরান
মিথ্যে ফেরত দিন
একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি গণনা করবে, k
res :=0
l :=0
r :=গণনায় উপস্থিত সমস্ত উপাদানের যোগফল
যখন l <=r, do
- m :=l + ফ্লোর অফ (r - l) / 2
- যদি সম্ভব (গণনা, m, k) সত্য হয়, তাহলে
  - l :=m + 1
  - res :=সর্বাধিক রেস এবং m
- অন্যথায়,
  - r :=m - 1
রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def possible(counts, groups, k):
   required = groups * k
   for i in range(len(counts)):
      temp = min(counts[i], groups, required)
      required -= temp
      if required == 0:
         return True
   return False

def solve(counts, k):
   res = 0
   l = 0
   r = sum(counts)
   while l <= r:
      m = l + (r - l) // 2
      if possible(counts, m, k):
         l = m + 1
         res = max(res, m)
      else:
         r = m - 1
   return res

counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k))

ইনপুট

[2, 3, 5, 3], 2