1. There is an island surrounded by oil mines. You will be given n companies and m oil mines having values. You have to distribute the mines to "n" companies in a fair manner. Remember the companies can have oil mines adjacent to each other and not in between of each other. After distributing them compute the difference of oil mines from the company getting highest and company getting lowest. This number should be minimum.(then only the distribution can be termed as fair).
Example
Input
2
2 4
6 13 10 2
2 4
6 10 13 2
output
5
1
3
0 0 100 100 20 30 50 50 70 70
output: The length of the optimized path taken.
For above input, the output is 200
Example
Input
2
2 4
6 13 10 2
2 4
6 10 13 2
output
5
1
2. A delivery boy wants to deliver some items on his way from office to home. You need to find the optimized path he should take from office to home and deliver all his deliveries on his way.
It is 101 X 101 grid. Office, home , delivery points are represented via coordinated (x,y) where 0 <= x <= 100, 0 <= y <= 100.
Distance between two points (x1, y1) and (x2,y2) is computed as |x1 - x2| + |y1 - y2|
You need to find the optimized path from office to home covering all delivery locations and return the optimized path length as output.
You will be given the input in the 2 lines
First Line - N (no. of delivery locations)
Second Line - (x,y) coordinates of office, followed by home, followed by all N delivery locations.
3
0 0 100 100 20 30 50 50 70 70
output: The length of the optimized path taken.
For above input, the output is 200
give me the solution
ReplyDelete#include
ReplyDelete#include
int
main ()
{
int i, k = 0, N, t, sm = 99999, Answer = 0, temp = 0;
int X, Y, SX, SY, TX, TY, CX[100], CY[100], DX[100], DY[100];
scanf ("%d", &N);//number of customer
scanf ("%d %d", &SX, &SY); //coordinates of office
scanf ("%d %d", &TX, &TY);//coordinates of home
for (i = 0; i < N; i++)
{ //customers coordinates
scanf ("%d %d", &CX[i], &CY[i]);
DX[i] = CX[i];
DY[i] = CY[i];
}
printf ("N=%d SX=%d SY=%d TX=%d TY=%d ", N, SX, SY, TX, TY);
for (i = 0; i < N; i++)
{
printf ("CX[%d]=%d CY[%d]=%d", i, CX[i], i, CY[i]);
}
printf ("xxxxxxx first phase xxxxxxxx");
printf ("\n");
// first phase :when delivery boy has to chose the address of closest customer
for (i = 0; i < N; i++)
{
printf ("for i=%d ", i);
t = abs (SX - CX[i]) + abs (SY - CY[i]);
printf (" t=%d sm=%d ", t, sm);
if (t < sm)
{
sm = t;
printf ("new sm=%d ", sm);
X = CX[i];
Y = CY[i];
temp = i;
}
printf ("\n");
}
DX[temp] = 99999;
DY[temp] = 99999;
Answer = Answer + sm;
printf ("Answer=%d ", Answer);
printf ("\n");
printf ("xxxxxxx second phase xxxxxxxx");
printf ("\n");
//Second phase:The delivery route
SX = X;
SY = Y;
while (k < N - 1)
{
sm = 99999;
printf ("for new SX=%d and SY=%d", SX, SY);
printf ("\n");
for (i = 0; i < N; i++)
{
if ((SX == CX[i] && SY == CY[i])||(DX[i] == 99999 && DY[i] == 99999))
{
continue;
}
else
{
t = abs (SX - CX[i]) + abs (SY - CY[i]);
printf (" t=%d sm=%d ", t, sm);
if (t < sm)
{
sm = t;
printf ("new sm=%d ", sm);
X = CX[i];
Y = CY[i];
temp = i;
}
}
}
DX[temp] = 99999;
DY[temp] = 99999;
Answer = Answer + sm;
printf (" Answer=%d ", Answer);
printf ("\n");
SX = X;
SY = Y;
k++;
}
printf ("xxxxxxx third phase xxxxxxxx");
printf ("\n");
//third phase: when delivery boy at the last customer's address closest to home
SX = TX;
SY = TY;
t = abs (SX - CX[temp]) + abs (SY - CY[temp]);
Answer = Answer + t;
printf ("shortest distance(Answer)=%d ", Answer);
return 0;
}
U GUYS CAN KEEP ONLY THE LAST PRINTF OF SHORTEST DISTANCE AND REMOVE REST OF THE PRINTFs , I HAVE CONSIDERED VALUE 99999 AS A NULL
AND BY THE WAY THIS PROGRAM IS IN C.