South Central USA Regional Programming Contest

Problem #3: Treasure Hunters

  
Introduction

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:

  1. Start line - A single line, "START"
  2. Number of Treasures - A single line with a single integer, t, where 1 <= t <= 8, indicating the number of treasures.
  3. Number of Hunters - A single line with a single integer, h, where 1 <= h <= 6, indicating the number of treasure hunters.
  4. Treasure Value List - A series of h lines, one for each hunter in sequence (line 1 for hunter 1, line 2 for hunter 2, etc.). Each line contains a space-separated list of estimated treasure values for that hunter. The first estimate on each line is for treasure 1, the second is for treasure 2, etc., and an estimate for each treasure will appear for every hunter. Each estimate will be a positive integer strictly less than 10000.
  5. End line - A single line, "END"

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

The statements and opinions included in these pages are those of 2001 South Central USA Regional Programming Contest Staff only. Any statements and opinions included in these pages are NOT those of Louisiana State University, LSU Computer Science, LSU Computing Services, or the LSU Board of Supervisors.
© 1999,2000,2001 Isaac W. Traxler