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

মান লিজিয়ে একটি ফেরিস হইল আছে যাতে চারটি কেবিন রয়েছে এবং প্রতিটি কেবিনে চারজন যাত্রী বসে পারে। হইলটি কাউন্টার-ক্লকওয়াইজ ঘুরে এবং প্রতিটি রোটেশনের জন্য run টাকা খরচ হয়। আমাদের একটি অ্যারে আছে cust যাতে n আইটেম রয়েছে এবং i-তম আইটেম নির্দেশ করে i-তম রোটেশনের আগে কতজন লোক কতেনে। হইলে চড়তে হলে প্রতিটি যাত্রীকে board টাকা দিতে হয়, এবং ততটুকু টাকা একবার এন্টি-ক্লকওয়াইজ রোটেশনের জন্য। লাইনে থাকা মানুষ খালি সিট থাকলে কতেনে থাকবেন না। দেওয়া ডেটা থেকে প্রফিট সর্বোচ্চ করার জন্য ন্যূনতম রোটেশন সংখ্যা বের করতে হবে।

যেমন, ইনপুট হলে cust = [6,4], board = 6, run = 4, তবে আউটপুট হবে 3।

প্রথমে ৬ জন লাইনে আছে। ৪ জন প্রথম কেবিনে চড়ে, বাকি কেতে থাকে। হইল ঘুরে, ২য় কেবিন আসে। মাঝপথে ৪ জন আর কতেছে। এবার ৪ জন ২য় কেবিনে চড়ে। আবার হইল ঘুরে, বাকি ৩ জন ৩য় কেবিনে চড়ে। তাই ন্যূনতম ৩ রোটেশন লাগল সবাইকে সার্ভ করতে। এই রোটেশনগুলো থেকে সর্বোচ্চ প্রফিট: (10 * 6) - (3 * 4) = 48।

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

res := -1, mst := 0, tmp := 0, wt := 0
cust-এ প্রতিটি (idx, val) এর জন্য:
- wt += val
- chg := min(4, wt)
- wt -= chg
- tmp += chg * board - run
- যদি mst < tmp হয়, তবে res := idx+1, mst := tmp
x, y := divmod(wt, 4)
যদি 4*board > run হয়, তবে res += x
যদি y*board > run হয়, তবে res += 1
res রিটার্ন করুন।

উদাহরণ

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

def solve(cust, board, run):
    res = -1
    mst = 0
    tmp = 0
    wt = 0
    for idx, val in enumerate(cust):
        wt += val
        chg = min(4, wt)
        wt -= chg
        tmp += chg * board - run
        if mst < tmp:
            res, mst = idx + 1, tmp
    x, y = divmod(wt, 4)
    if 4 * board > run:
        res += x
    if y * board > run:
        res += 1
    return res

print(solve([6,4], 6, 4))

ইনপুট

[6,4], 6, 4