পাইথনে সিটির চক্রে ফুয়েল ট্যাঙ্ক ক্যাপাসিটি বিবেচনা করে সার্কুলার টুরের স্টার্টিং পয়েন্ট বের করা

n সিটি ০ থেকে n-1 পর্যন্ত নম্বরড। সিটি i থেকে (i+1)%n এ যাওয়া যায়। গাড়ির ফুয়েল ট্যাঙ্ক ক্যাপাসিটি cap। সিটি i-তে fuel[i] ফুয়েল পাওয়া যায় এবং i থেকে (i+1)%n যেতে cost[i] ফুয়েল লাগে। কতটি সিটি থেকে стар্ট করলে পুরো চক্র ঘুরে আবার সেই সিটিতে ফিরে আসা যায় তা বের করতে হবে।

উদাহরণ

ইনপুট: cap = 3, fuel = [3,1,2], costs = [2,2,2]

আউটপুট: 2

সিটি ০ এবং ২ থেকে শুরুর সম্ভব। সিটি ১ থেকে নয় কারণ ফুয়েল কম।

সমাধান পদ্ধতি

1. n := len(fuel)
2. req := [0]*n
3. ২ বার (k=0,1) ulta লুপ:
   • i = n-1 থেকে ০:
     • nexti = (i+1)%n
     • req[i] = max(0, req[nexti] + costs[i] - fuel[i])
     • যদি min(req[i] + fuel[i], cap) - costs[i] < req[nexti]: রিটার্ন ০
4. req-এ ০-এর সংখ্যা রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

def solve(cap, fuel, costs):
    n = len(fuel)
    req = [0] * n
    for k in range(2):
        for i in range(n-1, -1, -1):
            nexti = (i + 1) % n
            req[i] = max(0, req[nexti] + costs[i] - fuel[i])
            if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
                return 0
    return sum(1 for r in req if r == 0)

# টেস্ট
cap = 3
fuel = [3, 1, 2]
costs = [2, 2, 2]
print(solve(cap, fuel, costs))  # আউটপুট: 2

ইনপুট

3, [3,1,2], [2,2,2]

আউটপুট

2