Cars around a track

n cars (n <= 50) are positioned around a circular track.  The total amount of fuel in the cars is enough for one car to drive around the entire track.  It is required to find such a car.  For each car i, you are given f[i] (the distance which can be travelled wth thte fuel n the car) and d[] (the distance to the next car).
1. Prove that there exists at least one car, x, with enough fuel to get to the next car [2].
2. If the fuel from car y is transferred to car x and y is removed from the track, the problem remains the same with one less car.  Based on this observation, write code which reads values for n, f[i], d[i] (i=1, n) and prints the number of the car which can be used to drive around the track. [8]



/* transfer fuel from the car following i to car i, this car may not necessarily be the i+1th car, since cars are being
removed as fuel is transferred from them, so it is the current car following I at this time.
To handle this we create a circular list in the array so:

2

3

4

5

6

7

8

9

10

1

Location 1 contains 2 which is the next car number
Location 2 contains 3 the next car number and so on.
Let’s say Fuel gets transferred from car 4 then we remove the pointer to car 4 and transfer the value in the next cell
to this location so the array becomes:

2

3

4+5

0

6

7

8

9

10

1

for (int i=1; i<=m, i++){
read(x) = f[i]
read(y) = d[i]; //load data
}

for (int j=1; j<n; j++){ //remove n-1 cars

for (int i=1; i<=n; i++){
if (f[i] >= d[i])
break;
}

nc = (i mod n) + 1 //count circularly around cars
while (f [nc] ==0){ //car has been removed
nc = nc mod n + 1;
} // end while
f [i] += f[nc];
d[i] += d[nc]; //transfer fuel
f[nc] = 0;       // set fuel to 0 in car it has been taken from
}// end for