#4719. [USACO 1.2.2] gift1: Greedy Gift Givers
[USACO 1.2.2] gift1: Greedy Gift Givers
gift1: Greedy Gift Givers
任务 “gift1”：贪婪的送礼者**|
一组 NP（2 ≤ NP ≤ 10）个独特名字的朋友决定互相送钱作为礼物。这些朋友中的每一个都可能（也可能不）给其他朋友（部分或全部）一些钱（尽管有些人可能很吝啬，不给任何人钱）。同样，每个朋友也可能（也可能不）从其他朋友（部分或全部）那里收到钱。你的目标是推算出每个人收到的钱比他们送出的钱多多少。
送礼的规则可能与你预期的不同。每个人去银行（或任何其他钱的来源）获取一定数量的钱来送礼，并将这些钱平均分给所有他/她要送礼的人。没有分数钱可用，所以将 7 分给 2 个朋友，每个朋友得到 3，剩下 1 个——剩下的 1 个进入送礼者的 “账户”。所有参与者的礼物账户最初都是 0，会因送出的钱而减少，因收到的钱而增加。
在任何一组朋友中，有些人比其他人更慷慨（或者至少可能有更多的熟人），有些人比其他人更有钱。
已知：
- 一组朋友，没有人名字超过 14 个字符，
- 每个人在小组中用于礼物的花费金额，以及
- 每个人送礼的（子）朋友名单，
确定每个人最终得到多少钱。
重要说明
评分机器是一台使用标准 Unix 约定的 Linux 机器：换行是一个通常被称为 “\n” 的单个字符。这与 Windows 不同，Windows 用两个字符 “\r” 和 “\n” 结束行。不要让你的程序陷入这个陷阱！
程序名称：gift1
输入格式
| 行号 | 内容 |
|---|---|
| 1 | 一个整数，NP |
| 2..NP+1 | 第 i +1 行包含小组成员 i 的名字 |
| NP+2..结束 | NP 组按以下方式排列的行： |
| 每组的第一行告诉将要送礼的人的名字。 |
| 每组的第二行包含两个数字： - 分成礼物的金额（范围在 0..2000） - NGi（0 ≤ NGi ≤ NP），送礼者将要送礼的人数 |
| 如果 NGi 不为零，接下来的 NGi 行列出收礼人的名字；收礼人不会在单个送礼者的名单中重复。 |
示例输入（文件 gift1.in）
5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0
输出格式
输出是 NP 行，每行包含一个人的名字，后面跟着一个空格，然后是该人的净得或净失（final_money_value - initial_money_value）。名字应该按输入中从第 2 行开始的顺序打印。
所有礼物都是整数。每个人给每个朋友的金额相同，且尽可能多地满足这个约束条件。任何未送出的钱都由送礼者保留。
示例输出（文件 gift1.out）
dave 302
laura 66
owen -359
vick 141
amr -150
输出说明
五个名字：dave、laura、owen、vick、amr。 让我们为每个人 “拥有” 的钱（礼物）保持一个表格：
| dave | laura | owen | vick | amr |
| 0 | ||||
| 首先，'dave' 将 200 分给 'laura'、'owen' 和 'vick'。每人得到 66，剩下 2 个 | ||||
| -200+2 | +66 | 0 | ||
| → | ||||
| -198 | 66 | 0 | ||
| 其次，'owen' 给 'dave' 500： | ||||
| -198 +500 | 66 | 66 -500 | 66 | 0 |
| → | ||||
| 302 | 66 | -434 | 66 | 0 |
| 第三，'amr' 将 150 分给 'vick' 和 'owen'： | ||||
| 302 | 66 | -434 +75 | 66 +75 | -150 |
| → | ||||
| 302 | 66 | -359 | 141 | -150 |
| 第四，'laura' 将 0 分给 'amr' 和 'vick'；无变化： | ||||
| 302 | 66 | -359 | 141 | -150 |
| 最后，'vick' 不给任何人 0： | ||||
| dave | laura | owen | vick | amr |
| 302 | 66 | -359 | 141 | -150 |