Solve the Turnpike Problem solved by 50

July 29, 2015, 1:03 a.m. by Rosalind Team

If A = (a1 = 0, a2, ... , an) is a set of n points on a line segment in increasing order (a1 < a2 < · · · < an), then $\Delta$A denotes the collection of all pairwise differences between points in A. For example, if A = (0, 2, 4, 7), then

$\Delta$A = (7, 5, 4, 3, 2, 2, 0, 0, 0, 0, 2, 2, 3, 4, 5, 7).

The following problem asks us to reconstruct A from $\Delta$A.

Turnpike Problem

Given all pairwise distances between points on a line segment, reconstruct the positions of those points.

Given: A collection of integers L.

Return: A set A such that ∆A = L.

Sample Dataset

-10 -8 -7 -6 -5 -4 -3 -3 -2 -2 0 0 0 0 0 2 2 3 3 4 5 6 7 8 10

Sample Output

0 2 4 7 10

Extra Dataset

Please login to solve this problem.