#P18347. Las Vegas

Las Vegas

Las Vegas

题目描述

Las Vegas 是一款容易上手的掷骰子桌游。玩家把骰子放在不同赌场,在每个赌场中,拥有最多骰子且没有因数量相同而被移除的玩家获胜。这款游戏结合了运气和策略,并曾获 2012 年 Spiel des Jahres 提名。

现在考虑一个有 nn 个赌场、m+1m+1 名玩家的游戏。你是第 m+1m+1 名玩家,其他 mm 名玩家已经决定了各自在每个赌场中放入的骰子数量。已知第 jj 名玩家在第 ii 个赌场中放入了 ai,ja_{i,j} 个骰子。

你需要决定,对每个赌场 ii,自己放入多少个骰子 bib_i。当所有玩家都放置完毕后,每个赌场独立按照下列规则确定赢家:

  1. 如果至少两名玩家在该赌场放入的骰子数量相同,那么这些玩家在该赌场的骰子全部移除。这个规则适用于所有玩家,包括你。
  2. 移除后,在该赌场仍拥有最多骰子的玩家获胜。如果该赌场已经没有骰子,则没有赢家。

例如:

  • 某个赌场中,七名玩家的骰子数分别为 1,2,3,3,4,4,41,2,3,3,4,4,4。数量为 33 的两名玩家和数量为 44 的三名玩家的骰子都会被移除,剩下的骰子数为 1,2,0,0,0,0,01,2,0,0,0,0,0。原来放入 22 个骰子的玩家获胜。
  • 某个赌场中,四名玩家的骰子数分别为 2,3,2,32,3,2,3,则所有骰子都会被移除,该赌场没有赢家。

设第 jj 名玩家获胜的赌场数量为 wjw_j。你的目标是使自己的获胜场数至少与每个其他玩家一样多,即

wm+1≥wj(1≤j≤m).w_{m+1}\ge w_j\qquad(1\le j\le m).

在满足这个条件的前提下,最小化自己放入的骰子总数

∑i=1nbi.\sum_{i=1}^{n}b_i.

你不必严格超过其他玩家;如果所有玩家都没有获胜,目标条件同样成立。

输入格式

第一行包含一个整数 TT,表示测试数据组数。

对于每组测试数据:

第一行包含两个整数 n,mn,m,分别表示赌场数量和除你以外的玩家数量。

接下来 nn 行,第 ii 行包含 mm 个整数 ai,1,ai,2,…,ai,ma_{i,1},a_{i,2},\ldots,a_{i,m},表示其他玩家在第 ii 个赌场放入的骰子数。

输出格式

对每组测试数据输出一行,包含 nn 个以空格分隔的整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,表示你在各个赌场放入的骰子数。

要求 0≤bi≤1090\le b_i\le10^9,满足获胜场数条件,并且骰子总数最小。可以证明,在这个范围内总有最优答案。如果有多个最优方案,输出任意一个即可。

数据范围

  • 1≤T≤1001\le T\le100;
  • 1≤n,m≤501\le n,m\le50;
  • 0≤ai,j≤1080\le a_{i,j}\le10^8;
  • 每个输入文件中,满足 n>20n>20 或 m>20m>20 的测试数据最多有 33 组。

样例输入 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

样例说明

第一组测试数据中,你在第 11、33 个赌场获胜,玩家 22 在第 22、44 个赌场获胜。你们的获胜场数都是 22。

第二组测试数据中,你在第 33 个赌场获胜,玩家 44 在第 22 个赌场获胜,第 11 个赌场没有赢家。

第三组测试数据中,不放骰子即可使所有玩家都没有获胜。