পাইথনে বোর্ডকে বর্গাকারে কাটাতে ন্যূনতম খরচ বের করুন

সমস্যা বিবরণ

একটি বোর্ডের দৈর্ঘ্য p এবং প্রস্থ q। এটিকে p*q সংখ্যক বর্গাকারে কাটাতে হবে যাতে কাটার খরচ ন্যূনতম হয়। প্রতিটি এজের কাটার খরচ দেওয়া আছে।

উদাহরণস্বরূপ, X_slice = [3,2,4,2,5], Y_slice = [5,2,3] হলে আউটপুট হবে 65।

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

1. X_slice এবং Y_slice ডিসেন্ডিং অর্ডারে সর্ট করুন।
2. horizontal = 1, vertical = 1 শুরু করুন।
3. দুই পয়েন্টার i, j দিয়ে লুপ চালান:
   • যদি X_slice[i] > Y_slice[j] হয়, res += X_slice[i] * vertical, horizontal++, i++।
   • অন্যথায় res += Y_slice[j] * horizontal, vertical++, j++।
4. বাকি X_slice এবং Y_slice প্রসেস করুন।
5. res রিটার্ন করুন।

পাইথন কোড উদাহরণ

def minCost(X_slice, Y_slice, m, n):
    res = 0
    X_slice.sort(reverse=True)
    Y_slice.sort(reverse=True)
    horizontal = 1
    vertical = 1
    i = j = 0
    while i < m and j < n:
        if X_slice[i] > Y_slice[j]:
            res += X_slice[i] * vertical
            horizontal += 1
            i += 1
        else:
            res += Y_slice[j] * horizontal
            vertical += 1
            j += 1
    total = 0
    while i < m:
        total += X_slice[i]
        i += 1
    res += total * vertical
    total = 0
    while j < n:
        total += Y_slice[j]
        j += 1
    res += total * horizontal
    return res

m = 6
n = 4
X_slice = [3, 2, 4, 2, 5]
Y_slice = [5, 2, 3]
print(minCost(X_slice, Y_slice, m-1, n-1))  # আউটপুট: 65

ইনপুট

[3,2,4,2,5], [5,2,3]

আউটপুট

65