Soluție HackerRank pentru Hyperspace Travel, subdomeniul Geometry, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Hyperspace Travel
- Domeniu: Geometry
- Limbaj: Python 3
Challenge: Hyperspace Travel
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464740365
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/hyperspace-travel/problem
Cerință
A group of n friends living in an m-dimensional hyperspace want to meet up at some central location. The hyperspace is in the form of an m-dimensional grid, and each person can only move along grid lines. For example, to go from (0, 0) rightarrow (1, 1) in a 2-dimensional space, one possible route is (0, 0) rightarrow (0, 1) rightarrow (1, 1) for a total distance traveled of 2 units.
Given the coordinates, (X[0, 1, …, m - 1]), for n friends, find a point at which all n friends can meet such that the total sum of the distances traveled by all n friends is minimal. If there are multiple such points, choose the lexicographically smallest one. The point P_1[0, 1, …, m - 1] is lexicographically smaller than P_2[0, 1, …, m - 1] if there exists such j lt m that forall i lt j,P_1[i] = P_2[i] and P_1[j]<P_2[j].
Input Format
The first line contains two space-separated integers describing the respective values of n and m.
Each line i of the n subsequent lines contains m space-separated integers describing the respective coordinates (i.e., x_0, x_1, …, x_m - 1) for friend i.
Output Format
Print m space-separated integers describing the coordinates of the meeting point.
Constraints
+ 1 ≤ n ≤ 10^4
+ 1 ≤ m ≤ 10^2
+ -10^9 ≤ x_i ≤ 10^9
Cod sursă
import sys
def main():
data = sys.stdin.buffer.read().split()
if not data:
return
it = iter(data)
n = int(next(it))
m = int(next(it))
cols = [[] for _ in range(m)]
for _ in range(n):
for j in range(m):
cols[j].append(int(next(it)))
ans = []
k = (n - 1) // 2 # lower median for lexicographically smallest minimizer
for j in range(m):
c = cols[j]
c.sort()
ans.append(str(c[k]))
sys.stdout.write(' '.join(ans))
if __name__ == '__main__':
main()