Question

The purpose of this C++ programming assignment is to practice using an array. This problem is selected from the online contest problem archive, which is used mostly by college students worldwide to challenge their programming ability and to prepare themselves for attending programming contests such as the prestige ACM International Collegiate Programming Contest.

For your convenience, I copied the description of the problem below with my note on the I/O and a sample executable.

Background
The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.

Problem
Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.

Input
The input consists of several test cases. The first line contains the number of test cases.

For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) s₁, s₂, ..., s_i, ..., sr where they live ( 0 < s_i < 30000 ). Note that several relatives could live in the same street number.

Output
For each test case, your program must write the the optimal Vito's house number and minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers s_i and s_j is d_ij = |s_i-s_j|. Note: The red font below indicates user input

Sample Input/output

Number of test case: 2

Test case #1
Number of relative: 2

Street numbers: 2 4

Vito's house number: 2

sum of distances: 2

Test case #2

Number of relative: 3

Street numbers: 2 4 6

Vito's house number: 4

sum of distances: 4

Note: If you input the above sample data from the keyboard, the output will be printed on your screen right after each test case.

Another sample input and output:

Number of test case: 1

Test case #1
Number of relative: 10

Street numbers: 2 12 23 10 3 40 20 19 4 10

Vito's house number: 10

sum of distances: 85

Answer 1

C++ code:

//=======================================================

#include<iostream>
#include<math.h>
using namespace std;

int main()
{
   int test;
   cout << "Number of test case: ";
   cin >> test;
   int t = 0;
   while (t<test)
   {
       t++;
       cout << "Test case #" << t << endl;
       cout << "Number of relative: ";
       int relative;
       cin >> relative;
       int *arr = new int[relative]; // arr store streat location of relative
       cout << "Street numbers: ";
       for (int i = 0; i < relative; i++)cin >> arr[i];
       //arr sorting
       for (int i = 1; i < relative; i++)
       {
           int key = arr[i];
           int j;
           for (j = i - 1; j >= 0; j--)
           {
               if (arr[j]>key) arr[j + 1] = arr[j];
               else break;
           }
           arr[j + 1] = key;
       }
       int mid;
       if (relative % 2 == 0) mid = relative / 2 - 1;
       else mid = relative / 2;
       int best_streat = arr[mid];

       int distance=0;
       for (int i = 0; i < relative; i++)
       {
           distance += abs(best_streat - arr[i]);
       }
       cout << "Vito's house number: " << best_streat<<endl;
       cout << "sum of distances:    " << distance << endl;
   }

system("pause");
   return 0;
}

sample input/output

//===========================================================

explanation: Optimal street for vito's house is median street of all relatives. In case of odd relative there is only single median but in case of even relative there are 2 median. vito can stay at any location sum of distance between vito house and relatives house will remain same. Median street have equal number of street at its both side. If we choose any random location (x) and there are uneven relatives on both side. Then he should move toward more relatives to decrease total distance because vito is reducing distance from more relatives and increasing distance from less relative.He will move till relatives around its street are equal.