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

## No comments:

## Post a Comment