South Central USA Regional Programming Contest
Problem #3: Treasure Hunters |
You've been a treasure hunter for a long time. You're pretty good at disarming traps, sneaking past the natives, and generally getting the goods while leaving your skin intact. That stuff doesn't really worry you, but what really raises a sweat is after each expedition there are always very tense arguments about how to split up the loot. You've worked with all kinds of characters and nobody ever agrees on what each piece of treasure is actually worth. You need to come up with a way of splitting the booty as fairly as possible.
Input
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 5 components:
Output
For each input data set, there will be exactly one output set, and there will be exactly one blank line separating output sets.
Each output set consists of multiple lines, where each line represents a hunter (listed in the same order as the corresponding input data set). Each line contains a list of the treasures given to that hunter followed by the total perceived cash value (by that hunter), of all the treasures they receive. Treasures will be listed in ascending order by treasure number, and all values on each line will be space-separated.
Treasures will be divided among the hunters in the fairest way possible. The "fairest" way to divide the treasure is defined to be the distribution with the minimum difference between the highest perceived total value and the lowest perceived total value of treasures received by any hunter. In other words, find the distribution that minimizes the difference between the hunter that gets the "most" and the hunter that gets the "least."
There will not be multiple "fair" distributions.
Sample Input
START 5 3 42 500 350 700 100 250 200 500 1000 75 150 400 800 800 150 END START 5 3 42 500 350 200 100 250 200 500 1000 75 150 400 800 800 150 END START 5 3 500 500 350 200 100 250 200 500 1000 75 150 400 800 800 150 END
Sample Output
4 700 3 5 575 1 2 550 1 4 5 342 3 500 2 400 1 2 1000 4 1000 3 5 950