Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Олимпиадные задачи на английском языке

04/02/2008 | Зима 2008 дорешивание (4B) |

08/02/2008 | Тренировка (задачи Benelux APC 2006) (B) |

*Ограничения: время – 10s/20s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

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:

Game|! | 1|! | 2|! | 3 |

Paul|! | 102|! | 86|! | 94 |

Ivo|! | 98|! | 73|! | 112 |

Nick|! | 95|! | 84|! | 125 |

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

`M_i`, 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 `i`th line should be two integers, separated by a single space: `m_i`, followed by `M_i`.

Sample Input

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

Sample Output

0 2 0 2 1 2 1 3 0 2 1 2