পাইথনে বয়سكেটে বল-এর ন্যূনতম সীমা খুঁজে বের করার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি অ্যারে আছে nums যেখানে i-তম এলিমেন্ট নির্দেশ করে nums[i] সংখ্যক বল ধারণকারী একটি বয়স্কেট। আরেকটি মান আছে mx। আমরা নিচের অপারেশন সর্বোচ্চ mx বার পারফর্ম করতে পারি:

বল থাকা যেকোনো একটি বয়স্কেট বাছাই করুন এবং সেটিকে কমপক্ষে একটি বল যুক্ত করে দুটি নতুন বয়স্কেটে ভাগ করুন।
এখানে পেনাল্টি হল একটি বয়স্কেটে সর্বোচ্চ বলের সংখ্যা।

অপারেশনগুলো করার পর পেনাল্টি ন্যূনতম করতে হবে। অতএব, অপারেশনগুলো করার পর ন্যূনতম সম্ভাব্য পেনাল্টি বের করতে হবে।

যেমন, ইনপুট হলে nums = [4,8,16,4] এবং mx = 4, তবে আউটপুট হবে 4 কারণ আমরা নিচের অপারেশনগুলো করতে পারি: প্রাথমিকভাবে বয়স্কেটগুলো হল [4,8,16,4]। ১৬ বল সম্পন্ন বয়স্কেটটি ভাগ করলে [4,8,8,8,4] হয়। তারপর ৮ বল সম্পন্ন প্রতিটি বয়স্কেটকে ৪ বল করে দুটি বয়স্কেটে ভাগ করলে অ্যারেটি হবে [4,4,4,8,8,4], তারপর [4,4,4,4,4,8,4] এবং অবশেষে [4,4,4,4,4,4,4,4]। এখানে ন্যূনতম ৪টি বল আছে, যা পেনাল্টি।

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

helper() ফাংশন ডিফাইন করুন। এটি target, mx নেবে।
যদি target == 0 হয়, তবে mx + 1 রিটার্ন করুন।
count := 0
nums-এ প্রতিটি num এর জন্য:
- count := count + (num - 1) // target
count <= mx রিটার্ন করুন।
মেইন মেথড থেকে:
left := max(sum(nums) // (len(nums) + mx), 1)
right := max(nums)
left < right থাকা পর্যন্ত:
- mid := (left + right) // 2
- যদি helper(mid, mx) সত্য হয়, তবে right := mid
- অন্যথায়, left := mid + 1
left রিটার্ন করুন।

উদাহরণ

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

def helper(target, mx):
    if target == 0:
        return mx + 1
    count = 0
    for num in nums:
        count += (num - 1) // target
    return count <= mx

def solve(nums, mx):
    left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
    while left < right:
        mid = (left + right) // 2
        if helper(mid, mx):
            right = mid
        else:
            left = mid + 1
    return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

ইনপুট

[4,8,16,4], 4