যেখান থেকে আমরা পাইথনে ভ্রমণ শুরু করতে পারি তার সূচনার সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন 0 থেকে n-1 পর্যন্ত n শহর রয়েছে এবং n নির্দেশিত রাস্তা রয়েছে। আমরা শহর i থেকে শহরে (i + 1) % n [0 থেকে 1 থেকে 2 থেকে .... থেকে N - 1 থেকে 0] ভ্রমণ করতে পারি। আমাদের একটা গাড়ি আছে। আমাদের গাড়ির ফুয়েল ট্যাঙ্কের ক্ষমতা ক্যাপ ইউনিট। এখানে জ্বালানীর একক জ্বালানী আছে যা আমরা শহর i এর শুরুতে ব্যবহার করতে পারি এবং শহর i থেকে (i + 1) % n যেতে গাড়িটির খরচ[i] একক জ্বালানী লাগে। আমাদের খুঁজে বের করতে হবে এমন কয়টি শহর আছে যেখান থেকে আমরা আমাদের গাড়ি শুরু করতে পারি, যাতে আমরা সমস্ত শহর ঘুরে দেখতে পারি এবং যে শহরে শুরু করেছি সেখানে পৌঁছতে পারি?

সুতরাং, যদি ইনপুট ক্যাপ =3 জ্বালানী =[3,1,2] খরচ =[2,2,2] এর মত হয়, তাহলে আউটপুট 2 হবে কারণ দুটি সম্ভাব্য সমাধান রয়েছে।

• আমরা শহর 0 থেকে শুরু করতে পারি, 3 ইউনিট জ্বালানী দিয়ে ট্যাঙ্কটি পূরণ করতে পারি এবং 2 ইউনিট জ্বালানি ব্যবহার করে শহর 1 এ ভ্রমণ করতে পারি। ট্যাঙ্কে একটি ইউনিট বাকি আছে। সিটি 1 এ 1 ইউনিট জ্বালানী নেওয়ার পরে, গাড়িতে 2 ইউনিট জ্বালানী রয়েছে এবং আমরা 2 ইউনিট জ্বালানী ব্যবহার করে শহর 2 এ ভ্রমণ করতে পারি। ফুয়েল ট্যাঙ্ক এখন খালি। সিটি 2 এ 2 গ্যালন জ্বালানি জ্বালানি করার পর, আমরা 2 গ্যালন জ্বালানি ব্যবহার করে শহর 0-এ ফিরে যাই।

• আমরা শহর 2 থেকে শুরু করতে পারি, 2 ইউনিট জ্বালানি দিয়ে গাড়িটি পূর্ণ করতে পারি এবং শহর 0 এ যাত্রা করতে পারি। তারপর শহর 0 থেকে 3 গ্যালন জ্বালানী জ্বালানি করার পরে, আমরা তারপর শহর 1 এ যাত্রা করি এবং আমাদের কাছে 1 ইউনিট জ্বালানী রয়েছে। তারপরে আমরা সিটি 1 এ 1 ইউনিট জ্বালানী জ্বালানি করতে পারি, এবং এখন 2 ইউনিট জ্বালানী আছে এবং শহর 2 এ ভ্রমণ করতে পারি।

যাইহোক, আমরা শহর 1 থেকে শুরু করতে পারি না, এখানে শুধুমাত্র 1 ইউনিট জ্বালানী রয়েছে, তবে সিটি 2 তে ভ্রমণ করতে 2 গ্যালন প্রয়োজন৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=জ্বালানির আকার
• req :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
• 0 থেকে 1 রেঞ্জের k-এর জন্য, করুন
  • n-1 থেকে 0 রেঞ্জের i এর জন্য, 1 দ্বারা হ্রাস করুন, করুন
    • পরবর্তী :=(i + 1) মোড n
    • req[i] :=সর্বাধিক 0 এবং req[পরবর্তী] + খরচ[i] - জ্বালানি[i]
    • যদি ন্যূনতম (req[i] + জ্বালানি[i] এবং ক্যাপ) - খরচ[i]
    • রিটার্ন 0

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))

ইনপুট

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

আউটপুট

2