#P18347. Las Vegas
Las Vegas
Las Vegas
题目描述
Las Vegas 是一款容易上手的掷骰子桌游。玩家把骰子放在不同赌场,在每个赌场中,拥有最多骰子且没有因数量相同而被移除的玩家获胜。这款游戏结合了运气和策略,并曾获 2012 年 Spiel des Jahres 提名。
现在考虑一个有 个赌场、 名玩家的游戏。你是第 名玩家,其他 名玩家已经决定了各自在每个赌场中放入的骰子数量。已知第 名玩家在第 个赌场中放入了 个骰子。
你需要决定,对每个赌场 ,自己放入多少个骰子 。当所有玩家都放置完毕后,每个赌场独立按照下列规则确定赢家:
- 如果至少两名玩家在该赌场放入的骰子数量相同,那么这些玩家在该赌场的骰子全部移除。这个规则适用于所有玩家,包括你。
- 移除后,在该赌场仍拥有最多骰子的玩家获胜。如果该赌场已经没有骰子,则没有赢家。
例如:
- 某个赌场中,七名玩家的骰子数分别为 。数量为 的两名玩家和数量为 的三名玩家的骰子都会被移除,剩下的骰子数为 。原来放入 个骰子的玩家获胜。
- 某个赌场中,四名玩家的骰子数分别为 ,则所有骰子都会被移除,该赌场没有赢家。
设第 名玩家获胜的赌场数量为 。你的目标是使自己的获胜场数至少与每个其他玩家一样多,即
在满足这个条件的前提下,最小化自己放入的骰子总数
你不必严格超过其他玩家;如果所有玩家都没有获胜,目标条件同样成立。
输入格式
第一行包含一个整数 ,表示测试数据组数。
对于每组测试数据:
第一行包含两个整数 ,分别表示赌场数量和除你以外的玩家数量。
接下来 行,第 行包含 个整数 ,表示其他玩家在第 个赌场放入的骰子数。
输出格式
对每组测试数据输出一行,包含 个以空格分隔的整数 ,表示你在各个赌场放入的骰子数。
要求 ,满足获胜场数条件,并且骰子总数最小。可以证明,在这个范围内总有最优答案。如果有多个最优方案,输出任意一个即可。
数据范围
- ;
- ;
- ;
- 每个输入文件中,满足 或 的测试数据最多有 组。
样例输入 1
3
4 3
3 3 2
2 7 5
3 5 2
1 6 4
3 4
100 100 100 1
0 0 0 1
100 100 100 1
1 4
20 0 20 0
样例输出 1
4 0 6 0
1 0 2
0
样例说明
第一组测试数据中,你在第 、 个赌场获胜,玩家 在第 、 个赌场获胜。你们的获胜场数都是 。
第二组测试数据中,你在第 个赌场获胜,玩家 在第 个赌场获胜,第 个赌场没有赢家。
第三组测试数据中,不放骰子即可使所有玩家都没有获胜。