|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
I - ICPC Scoreboard
Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)
Charles is the contest director for the ICPC Tumbolian regional contest. His responsibility is ensuring the contest flows smoothly, that the contest rules are applied fairly, and, of course, announcing the final contest ranking.
According to ICPC rules, a team with more solved problems ranks above a team with less solved problems. If two teams have the same number of solved problems, the team with the smaller total penalty ranks above the team with the larger total penalty (in case both teams have the same number of solved problems and the same penalty, Charles considers them as tied).
The total penalty for a team is the sum of all the problem penalties of the problems that team has solved. The problem penalty for a problem is $TP + EP \times FA$, where $TP$ is the time penalty
for that problem, $EP$ is the contest’s error penalty and $FA$ is the number of failed attempts at solving the problem before submitting a correct solution.
The time penalty for a problem is the time since the start of the contest, in minutes, that the team needed to solve the problem. The error penalty is a positive integer chosen by the contest director, designed to reward teams that submit correct solutions on the first attempt.
Charles wants to change the error penalty from the “standard” value of $20$ minutes to stir things up. To study the effects of that change on the final rankings, he wants to know the range of error penalties that don’t change the final standings.
In other words, if team $A$ is ahead of team $B$ in the original standings, then $A$ should be ahead of $B$ in the modified standings; if $A$ and $B$ are tied in the original standings, they should also be tied in the modified standings (the original standings are the ones obtained with an error penalty of $20$ minutes).
Charles has been very busy organizing the Tumbolian regional, so he asked you to make a program that will compute the range for him.
Input
The input contains several test cases. The first line of each test case contains two integers $T$ and $P$ separated by a single space, indicating the number of teams and the number of problems, respectively $(2 \leq T \leq 100, 1 \leq P \leq 10)$. Each one of the next $T$ lines describes the performance of a team. A team’s performance description is a line containing $P$ problem descriptions separated by single spaces. Teams are not necessarily given in order of their final standings.
Each problem description is a string $\texttt{“A/S”}$, where $A$ is an integer representing the number of attempts that the corresponding team made at solving that problem $(0 \leq A \leq 100)$, and $S$ is either $\texttt{“-”}$, if the team did not solve that problem, or an integer indicating the number of minutes it took for the team to submit a correct solution $(1 \leq S \leq 300)$. Attempts made after the first correct submission are not counted.
The end of input is indicated by $T = P = 0$.
The input must be read from standard input.
Output
For each test case in the input print two positive integers separated by a single space, indicating the smallest and largest error penalties that would not change the final ranking. If there is no upper bound for the error penalty, print a $\texttt{“*”}$ instead of the upper bound.
The output must be written to standard output.
Sample test(s)
Input
5 3
0/- 0/- 0/-
2/- 2/- 1/-
1/60 1/165 1/-
1/80 0/- 2/120
0/- 1/17 0/-
4 2
17/- 5/-
2/7 3/-
3/- 2/-
1/15 0/-
3 2
1/- 2/15
2/53 1/17
1/70 1/20
0 0
Output
1 24
9 *
20 20