当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3053:Bowling

题目描述
Last saturday, Paul, Ivo and Nick went to a bowling alley. The hired a lane for one hour, and played three games. In this casual game play, the guys were simply counting the number of games they won: the overall winner would be the one who won the most games. (In case of a tie, they would have had to figure out another way to pronounce the winner.)

This time, Paul won two games and Nick one, so Paul was pronounced the winner. Ivo wondered how it was possible he lost all three games even though he felt his scores were not too bad. So he looked again at the scoreboard and saw this:
Game123
Paul1028694
Ivo9873112
Nick9584125

Paul indeed won two games, and Nick one, but Ivo noted that if he would have played his games in another order, namely 112-98-73, he would have won the two games, and Paul none!

Ivo's remark is not as unreasonable as one might think at first glance: in bowling, each game is played independent of the other players, except perhaps for some psychological side effects. The successive scores of an individual player can also be assumed to be more or less independent and identically distributed.

Ivo wisely kept his remarks to himself last Saturday, but later he started to think about using his idea of 'potential number of wins' as a measure of performance. He concluded that it would also be interesting to know the minimum number of wins for each player. Also, it would be nice not only to allow permutation of the games of the player whose number of wins is being maximized or minimized, but also permutation of the games of the other players. Finally, Ivo has to define when exactly a player 'wins' a game: a player wins a game if and only if his score is strictly greater than the score of each of the other players.

Ivo asks you to write a program that calculates fro each player i:
  • mi, the minimal number of games player i would have won, regardless of the permutation of the scores of each individual player and
  • Mi, the maximal number of games player i could have won if the scores of each individual player were permuted optimally to that purpose

输入解释
The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
  • One line with two integers P and G, separated by a single space, that indicate the number of players and the number of games respectively(2 <= P <= 100, 2 <= G <= 1000).
  • P lines, one for each player, each with G integers, separated by single spaces: the successive scores for that player.
Each score is between 0 and 300 (both inclusive).
输出解释
For every test case in the input, the output should contain P lines, one for each player in the input. On the ith line should be two integers, separated by a single space: mi, followd by Mi.
输入样例
2
3 3
102 86 94
98 73 112
95 84 125
3 4
100 110 112 116
98 112 110 112
90 98 113 113
输出样例
0 2
0 2
1 2
1 3
0 2
1 2

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3053

最后修改于 2020-10-29T06:51:19+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000 65536