পাইথন ব্যবহার করে একটি বালতিতে বলের মধ্যে ন্যূনতম বল সর্বাধিক করার প্রোগ্রাম

ধরুন আমাদেরকে বেশ কয়েকটি বালতি এবং x নম্বর বল দেওয়া হয়েছে। যদি বলগুলিকে বালতিতে রাখা হয়, একটি বিশেষ শক্তি তাদের মধ্যে কাজ করে এবং আমাদের দুটি বলের মধ্যে সর্বনিম্ন বল সর্বাধিক করার উপায় খুঁজে বের করতে হবে। p এবং q অবস্থানের একটি বালতিতে দুটি বলের মধ্যে বল হল |p - q|। আমাদের দেওয়া ইনপুট হল অ্যারে যেখানে বালতির অবস্থান এবং বলের সংখ্যা x। আমাদের তাদের মধ্যে ন্যূনতম বল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় pos =[2, 4, 6, 8, 10, 12], x =3, তাহলে আউটপুট হবে 4।

বলগুলিকে 12টি বালতিতে প্রদত্ত অবস্থানে রাখা যেতে পারে। তিনটি বলকে 4, 8, এবং 12 পজিশনে রাখা যেতে পারে এবং তাদের মধ্যে পাওয়ার হবে 4। এই মানটি আর বাড়ানো যাবে না।

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

একটি ফাংশন ball_count() সংজ্ঞায়িত করুন। এটি d
লাগবে
- এবং :=1
- curr :=pos[0]
- 1 থেকে n রেঞ্জের জন্য, করুন
  - যদি pos[i] - curr>=d, তাহলে
    - ans :=ans + 1
    - curr :=pos[i]
- উত্তর ফেরত দিন
n :=অবস্থানের আকার
তালিকা pos
সাজান
বাকি :=0
ডান :=pos[-1] - pos[0]
যখন বামে <ডানে, কর
- মধ্য :=ডান - ফ্লোর মান((ডান - বাম) / 2)
- যদি ball_count(mid)>=x, তাহলে
  - বাম :=মধ্য
- অন্যথায়,
  - ডান:=মধ্য - 1
বাম দিকে ফিরে যান

উদাহরণ

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

def solve(pos, x):
   n = len(pos)
   pos.sort()

   def ball_count(d):
      ans, curr = 1, pos[0]
      for i in range(1, n):
         if pos[i] - curr >= d:
            ans += 1
            curr = pos[i]
      return ans

   left, right = 0, pos[-1] - pos[0]
   while left < right:
      mid = right - (right - left) // 2
      if ball_count(mid) >= x:
         left = mid
      else:
        right = mid - 1
   return left

print(solve([2, 4, 6, 8, 10, 12], 3))

ইনপুট

[2, 4, 6, 8, 10, 12], 3