编程介的小学生 2017-08-03 08:22 采纳率: 20.5%
浏览 720
已采纳

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:

Start line - A single line, "START"

Number of Treasures - A single line with a single integer, t, where 1 <= t <= 8, indicating the number of treasures.

Number of Hunters - A single line with a single integer, h, where 1 <= h <= 6, indicating the number of treasure hunters.

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.

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

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-08-03 16:29
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型