পাইথনে কে ঘন্টায় পাথর অপসারণের হার খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে পাইল নামক সংখ্যার একটি তালিকা এবং একটি মান k আছে। পাইলস [i] প্রতিনিধিত্ব করে, স্তূপের উপর পাথরের সংখ্যা i. প্রতি ঘন্টায়, আমরা যেকোন স্তূপ নির্বাচন করি এবং সেই স্তূপ থেকে r সংখ্যক পাথর অপসারণ করি। যদি আমরা r-এর চেয়ে কম পাথরের একটি গাদা বাছাই করি, তবে স্তূপটি পরিষ্কার করতে এখনও এক ঘন্টা সময় লাগে। আমাদের r এর ন্যূনতম মান খুঁজে বের করতে হবে, যাতে আমরা k ঘন্টার কম বা সমান সময়ে সমস্ত পাথর অপসারণ করতে পারি।

সুতরাং, যদি ইনপুটটি পাইলস =[3, 6, 4] k =5 এর মত হয়, তাহলে আউটপুট হবে 3, কারণ, r =3টি পাথর প্রতি ঘন্টায়, আমরা 2 ঘন্টার মধ্যে দ্বিতীয় পাইলটি পরিষ্কার করতে পারি, তারপর 2 ঘন্টার মধ্যে তৃতীয়, এবং 1 ঘন্টার মধ্যে প্রথম গাদা পরিষ্কার করুন৷

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

l :=1
h :=সর্বাধিক পাইলস
r :=h
একটি ফাংশন turns() সংজ্ঞায়িত করুন। এটি r
তালিকায় উপস্থিত সকল উপাদানের যোগফল (পাইলে প্রতিটি b এর জন্য b/r এর সিলিং) সহ
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
যখন l
মধ্য :=(l + h) / 2 এর তল
যদি মোড় (মধ্য)> k হয়, তাহলে
- l :=মধ্য + 1
অন্যথায়,
- h :=মধ্য
- r :=সর্বনিম্ন r এবং মধ্য

রিটার্ন r

উদাহরণ

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

from math import ceil
def solve(piles, k):
   l = 1
   h = max(piles)
   r = h

   def turns(r):
      return sum(ceil(b / r) for b in piles)
   while l < h:
      mid = (l + h) // 2
      if turns(mid) > k:
         l = mid + 1
      else:
         h = mid
         r = min(r, mid)
   return r

piles = [3, 6, 4]
k = 5
print(solve(piles, k))

ইনপুট

[3, 6, 4], 5