পাইথনে বাল্টিতে বল রেখে ন্যূনতম ফোর্স সর্বোচ্চ করার প্রোগ্রাম

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

যেমন, ইনপুট হলে pos = [2,4,6,8,10,12], x = 3, তবে আউটপুট হবে 4।

বলগুলো পজিশন ৪, ৮, ১২-এ রাখলে তাদের মধ্যে ফোর্স হবে ৪, যা আর বাড়ানো যাবে না।

সমাধানের ধাপসমূহ

ball_count(d) ফাংশন ডিফাইন করুন:
- ans := 1, curr := pos[0]
- i = 1 থেকে n-1 পর্যন্ত: যদি pos[i] - curr >= d হয়, তবে ans += 1, curr = pos[i]
- ans রিটার্ন করুন।
n := len(pos)
pos.sort()
left := 0, right := pos[-1] - pos[0]
left < right থাকা পর্যন্ত:
- mid := right - (right - left) // 2
- যদি ball_count(mid) >= x হয়, তবে left := mid
- অন্যথায়, right := mid - 1
left রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

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