পাইথনে পার্কোর আর্টিস্ট যে সุดূর বিল্ডিংয়ে পৌঁছাতে পারে তা বের করার প্রোগ্রাম

মান লিজিয়ে n সংখ্যক বিল্ডিং আছে যাদের উঁচু ভিন্ন। একজন পার্কোর আর্টিস্ট কিছু ইট এবং ল্যাডারের সাহায্যে এক বিল্ডিং থেকে অন্যবিল্ডিংয়ে যেতে চায়। বিল্ডিংগুলোর উঁচু অ্যারে আকারে দেওয়া আছে। প্রতিটি ইট একটি ইউনিট লম্বা এবং আমাদের কিছু ইট দেওয়া আছে। ল্যাডার ও ইট শুধু একবার ব্যবহার করা যায়। পার্কোর আর্টিস্ট যে সুদূর বিল্ডিংয়ে পৌঁছাতে পারে সেটি বের করতে হবে।

যেমন, ইনপুট হলে heights = [5,8,7,6,2,3,1,4], bricks = 3, ladders = 2, তবে আউটপুট হবে 7।

শুরু ০ নম্বর বিল্ডিং থেকে। ৩টি ইট দিয়ে ১ নম্বর বিল্ডিংয়ে পৌঁছাল। ২, ৩, ৪ নম্বর বিল্ডিংয়ে জাম্প দিল (কারণ সেগুলো ছোট)। ৪ থেকে ৫-এ ল্যাডার দিয়ে গেল। ৫ থেকে ৬-এ জাম্প দিল (ছোট)। শেষ ল্যাডার দিয়ে ৭ নম্বর বিল্ডিংয়ে পৌঁছাল।

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

temp := হিপ (min-heap)
i = 1 থেকে len(heights)-1 পর্যন্ত:
- dist := heights[i] - heights[i-1]
- যদি dist > 0 হয়, তবে:
  - bricks -= dist
  - heappush(temp, -dist)
  - যদি bricks < 0 হয়, তবে:
    - ladders -= 1
    - bricks -= heappop(temp) (সর্বোচ্চ dist বাদ দেওয়া)
    - যদি bricks < 0 or ladders < 0 হয়, তবে return i-1
len(heights) - 1 রিটার্ন করুন।

উদাহরণ

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

from heapq import heappush, heappop
def solve(heights, bricks, ladders):
    temp = []
    for i in range(1, len(heights)):
        dist = heights[i] - heights[i - 1]
        if dist > 0:
            bricks -= dist
            heappush(temp, -dist)
            if bricks < 0:
                ladders -= 1
                bricks -= heappop(temp)
                if bricks < 0 or ladders < 0:
                    return i - 1
    return len(heights) - 1

print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))

ইনপুট

[5, 8, 7, 6, 2, 3, 1, 4], 3, 2