This is an extension of a classic puzzle.
You have a circular road, with $n$ petrol bunks (or gas stations as called in America) located somewhere along the road. You are given the length of each segment of the road, which is between two petrol bunks. You are also given the amounts of petrol left in each bunk. You are also told that the total amount of petrol is just enough to complete exactly one lap of the circular road, using a car that starts with an empty tank. The car has infinite capacity and you fill whatever you can when you reach a petrol bunk.
Now given a car with an empty tank, you need to find out in $O(n)$ time, all the possible starting points which will allow you to complete the lap. [The classic puzzle was to prove that there is a such a starting point].
The petrol bunks are numbered $1$ to $n$, and you are given an array $p[1, \dots, n]$ of the amounts of petrol, and a distance array $d[1, \dots, n]$ of the distances between the petrol bunks ($d[i] = $ distance between $p[i]$ and $p[i+1]$). The output will be a list of numbers between $1$ and $n$, denoting the petrol bunks you can start at.
Assume that one unit of petrol covers exactly one unit of distance.
[Solution]
You have a circular road, with $n$ petrol bunks (or gas stations as called in America) located somewhere along the road. You are given the length of each segment of the road, which is between two petrol bunks. You are also given the amounts of petrol left in each bunk. You are also told that the total amount of petrol is just enough to complete exactly one lap of the circular road, using a car that starts with an empty tank. The car has infinite capacity and you fill whatever you can when you reach a petrol bunk.
Now given a car with an empty tank, you need to find out in $O(n)$ time, all the possible starting points which will allow you to complete the lap. [The classic puzzle was to prove that there is a such a starting point].
The petrol bunks are numbered $1$ to $n$, and you are given an array $p[1, \dots, n]$ of the amounts of petrol, and a distance array $d[1, \dots, n]$ of the distances between the petrol bunks ($d[i] = $ distance between $p[i]$ and $p[i+1]$). The output will be a list of numbers between $1$ and $n$, denoting the petrol bunks you can start at.
Assume that one unit of petrol covers exactly one unit of distance.
[Solution]
No comments:
Post a Comment