Question

John misses his bus and has to walk all his way from home to school. The distance between his school and home is D units. He starts his journey with an initial energy of K units. His energy decreases by 1 unit for every unit of distance walked. On his way to school, there are N juice stalls. Each stall has a specific amount of juice in liters. His energy increases by 1 unit for every liter of juice he consumes. Note that in order to keep him walking he should have non-zero energy. Write an algorithm to help John figure out the minimum number of juice stalls at which he should stop to successfully reach the school. In case he can't reach the school, the output will be -1.

Answer 1

Explanation:

def visited(dist,lit,distance,initEnergy):

distance_covered = 0

i = 0

while i < len(dist) and initEnergy>= dist[i]-distance_covered and distance_covered <= distance :

if i == 0:

a = dist[i]

else:

a = dist[i]-dist[i-1]

distance_covered = distance_covered + initEnergy

initEnergy = initEnergy - a + lit[i]

i+=1

dist_left = distance_covered + initEnergy

if dist_left >= distance:

return i

else:

return -1

please change the name of function as given in the problem...

please change the name of function as given in the problem...Thank you

Answer 2

Answer:

class Solution(object):

   def minRefuelStops(self, target, startFuel, stations):

       dp = [startFuel] + [0] * len(stations)

       for i, (location, capacity) in enumerate(stations):

           for t in xrange(i, -1, -1):

               if dp[t] >= location:

                   dp[t+1] = max(dp[t+1], dp[t] + capacity)

       for i, d in enumerate(dp):

           if d >= target: return i

       return -1

explanation:

Algorithm

Let's replace dp as we take into account every station in order. With no stations, in reality we will get a most distance of startFuel with zero refueling stops.

Now let's study the replace step. When including a station station[i] = (vicinity, ability), any time we may want to attain this station with t refueling stops, we will now attain ability in addition with t+1 refueling stops.

For example, if we may want to attain a distance of 15 with 1 refueling stop, and now we introduced a station at vicinity 10 with 30 liters of fuel, then we may want to doubtlessly attain a distance of forty five with 2 refueling stops.

#SPJ2