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

建议使用的浏览器:

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

1940:ICPC Scoreboard

题目描述
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 ×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.
输入解释
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 <= T <= 100, 1 <= P <= 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 “A/S”, where A is an integer representing the number of attempts that the corresponding team made at solving that problem (0 <= A <= 100), and S is either “-”, 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 <= S <= 300). Attempts made after the first correct submission are not counted.
The end of input is indicated by T = P = 0.
输出解释
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 “*” instead of the upper bound.
输入样例
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
输出样例
1 24
9 *
20 20
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-1940

最后修改于 2020-10-25T22:49:05+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/1000MS(Java/Others) 32768/32768K(Java/Others)