Tuesday, January 18, 2011

Fixing the pipeline

We have to make a pipeline (gas pipeline). We have some pieces of pipes that is on the same line we want the pipeline on. But they are scattered on the entire line and are different sizes-

Now we have to move all the pieces and solder to make one single piece- so that we can order a single piece for the remaining legth-

Now we want to do this with least movement of the pieces- The larger the piece the more the cost- Cost is same for long distance or long distance because the most costly operation is loading and unloading the pipe on the truck-


Input:
3 integers each line separated by comma-
piece number , length of the piece, the starting position

Output-

2 integers each line separated by comma-
piece number, move to position-

While moving you can not move a large piece in a small gap of two pieces-

Sample input:
1, 10, 5
2, 30, 30
3, 90, 5
4, 130, 20

Sample output:
1, 0
2, 5
4, 10