পাইথনে একই দৈর্ঘ্যের k ফিতার সর্বাধিক দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে ধনাত্মক সংখ্যার একটি তালিকা রয়েছে, যা ফিতার দৈর্ঘ্যকে প্রতিনিধিত্ব করে এবং একটি মান k আছে। আমরা যতবার চাই ততবার ফিতা কাটতে পারি, আমাদের সবচেয়ে বড় দৈর্ঘ্যের r খুঁজে বের করতে হবে যাতে আমাদের r দৈর্ঘ্যের k ফিতা থাকতে পারে। যদি আমরা এই ধরনের সমাধান খুঁজে না পাই, ফিরে আসুন -1.

সুতরাং, যদি ইনপুটটি ফিতার মত হয় =[1, 2, 5, 7, 15] k =5, তাহলে আউটপুট হবে 5, যেহেতু আমরা 15 সাইজের ফিতাটিকে 5 দৈর্ঘ্যের 3 টুকরো করে কাটতে পারি। তারপর সাইজ 7 এর ফিতাটিকে 2 এবং 5 আকারে কাটুন। এবং 5 সাইজের আরেকটি ফিতা আছে, তাই আমরা 5 সাইজের মোট 5টি ফিতা পাচ্ছি।

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

• বামে :=0
• ডান :=সর্বাধিক ফিতা
• যখন বাম <ডানে, কর
  • মধ্য :=তল (বাম + ডান + 1) / 2
  • যদি তালিকায় উপস্থিত সমস্ত উপাদানের যোগফল থাকে (রিবনে প্রতিটি রিবনলেনের জন্য রিবনলেনের মেঝে / মাঝামাঝি ফিতা যা কমপক্ষে k হয়), তাহলে
    • বামে :=মধ্য
  • অন্যথায়,
    • ডান:=মধ্য - 1
• যদি বামে অ-শূন্য হয়, তাহলে
  • বাম দিকে ফিরুন
• রিটার্ন -1

উদাহরণ

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

def solve(ribbons, k):
   left = 0
   right = max(ribbons)
   while left < right:
      mid = (left + right + 1) // 2
      if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
         left = mid
      else:
         right = mid - 1
   if left:
      return left
   return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

ইনপুট

[1, 2, 5, 7, 15], 5

আউটপুট

5