How to solve this programming contest exercise?

Question

I need some advice, because i dont know how to solve this problem.

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=796

Answer 1

You can process streets and avenues separately.

For each direction, the optimal position is the one where the total distance to friend homes is the shortest.

For example, if you have a list with friend home streets called homeStreets you can iterate over (total street distances , street number) and pick the tuple with the minimum distance:

minDist,streetNumber = min( (sum(abs(sn-hs) for hs in homeStreets),sn) for sn in range(1,streetCount+1) )

you can use the same approach with avenues.