Challenge 04: Bear's Vents

Back when the instructor lived in Dublin Village, he managed to let his housemate convince him that his friend should be able to have a dog ¹.

This dog's name was Bear. Being an awesome husky, Bear sort of does whatever she wants. For instance, she just loves chilling out on top of the air conditioning vents in the house; they keep her cool and relaxed. Fortunately for Bear, there are vents in every room of the house, all lined up against the wall as so:

|| [vent]   [vent]    [vent] ||

Since huskies tend to be active and energetic dogs, Bear often gets restless and moves from one vent to another. Paradoxically, she also displays some laziness, and hates moving too much once she is in her relaxed state. Moreover, after moving to one vent, Bear always returns to her original one.

Your job is to figure out the optimal vent for each room that minimizes the total distance from that optimal vent to all the others.

Once you have figured out this information, Bear will know which vent to start at in each room, thus keeping herself cool and relaxed and not having to expend too much energy.

Input

Each line in the input represents a room. The first string is the name of the room, which is followed by the number of vents in the room (no more than 10) and then the distances of the vents from wall. Note, that since the vents are lined up against the wall, these can be considered linear distances. Likewise, some rooms may have multiple vents at the same location.

Example Input

Living 2 4 2
Ryan's 3 2 4 7

Output

For each room, output the name of the room, the location of the optimal vent, and the minimal sum of distances from the optimal vent to each of the other vents. Distances between two vents v_i and v_j is d_ij = | v_i - v_j |. In the case of multiple optimal vents, select the one closest to the wall (smallest v_i).

Example Output

Living 2 2
Ryan's 4 5

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa17-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge04               # Create and checkout challenge02 branch

$ $EDITOR challenge04/program.cpp           # Edit your code

$ git add challenge04/program.cpp           # Stage your changes
$ git commit -m "challenge04: done"         # Commit your changes

$ git push -u origin challenge04            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge04 assignment ...
Submitting challenge04 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge02/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/challenge04
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 02 TA List to determine your corresponding TA for the merge request.