uva online judge vito's family problem solution python | uva 10041

The vito's family problem (uva 10041) is a sorting problem in programming challenges from competitive programming. Which can be stated as (from online judge)

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.

Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem. The distance between two street numbers si and sj is dij = |si −sj|.

Sample Input

2
2 2 4
3 2 4 6

Sample Output

2
4

Explanation

Given random sequence of vito's relatives as input [number of relatives] [relatives distances] (relative name = distance of relative from vito's room) we have to sort out and find the best way to visit all relatives in minimum time.

We can do it in two ways:

1) find absolute difference between each relative and vito's room

2) find absolute difference between middle distance among all relatives and vito's room

The out of above two methods will be same, but rather using method 1, we will prefer method 2 since it is faster and short.

Code

no_case = int(input())

while (no_case):

    temp = input().split(" ")

    print(temp)

    r = temp[0]

    temp.remove(r)

    r = int(r)

    for i in range(0, r):

        temp[i] = int(temp[i])

    temp.sort()

    mid = temp[r // 2]

    ans = 0

    for i in temp:

        ans += abs(i - mid)

    print(ans)

    no_case -= 1

Here, first we remove list element at 0th index, since it only shows number of relatives. Then we find middle relative distance and store it in 'mid' variable.

Then just find and add absolute differences between middle relative and all other relatives in 'ans' variable and print it. That's it.

Hope, this article found helpful to you, thank you. 

Related keywords: vito's family, vitos family problem, vitos family uva, vitos family online judge, vitos family solution, vitos family explanation, vitos family source code, vitos family python, vitos family programmng challenge, uva 10041, uva 10041 solution python.