-->
当前位置:首页 > 题库 > 正文内容

编程题:数学分析

Luz3年前 (2022-09-05)题库294
一场古老的编程竞赛即将到来,它正是由$$ACM$$(梅特科维奇航空中心)组织的。正是$$N$$支队伍将角逐大奖,其中有一支克罗地亚金曲三重奏:保拉、马林和乔西普。竞赛形式是标准的,当飞行员执行特技飞行动作时,副驾驶阅读问题陈述,并试图将解决方案传送给安全地贴在飞机外部的主程序员。

比赛由$$M$$个不同的任务组成,各小组(不增加)按已解决任务的数量排序。具有相同数量已解决任务的团队按所谓的惩罚时间排序(非递减)。某个团队的惩罚时间是他们在每个正确解决的任务中完成的惩罚时间的总和。正确解决的任务的惩罚时间等于团队解决该任务(从比赛开始)所需的时间,对于每个错误提交的任务解决方案,额外增加$$20$$分钟。对于已经解决的问题,任何团队都不会尝试提交解决方案,对于某项任务,每个团队最多提交$$9$$份解决方案。如果一些球队有相同数量的解决问题和相同的处罚时间,他们将按字母顺序排列在最终排名中。

比赛持续五个小时。在前四个小时内,所有团队都可以获得排名,并包含关于每个团队每个任务状态的信息(提交的数量、是否解决以及何时解决)。在这四个小时内,团队的顺序将在每次提交后自动更新。然而,在最后一个小时,排名被冻结,也就是说,在评判新提交的参赛作品后,参赛队伍的顺序没有更新。在这段时间里,每个团队都知道自己提交的意见的判断,但他们不知道其他团队提交的意见的判断。他们只知道其他团队提交了哪些任务,提交了多少次,以及每个任务的最后一次提交时间。

比赛结束了,排名应该很快解冻。我们的英雄,名为$$NijeZivotJedanACM$$的团队需要你的帮助。他们想知道,在积分榜解冻后,他们最终可能在记分牌上的最差位置是什么。帮帮他们!

### 输入格式:

第一行包含整数$$N(1≤N≤1000)$$和$$M(1≤M≤15)$$ 表示$$N$$个队伍。

接下来的N行代表冻结的排名。每一行以团队名称(由小写和大写英文字母组成的字符串,最多由$$20$$个字符组成,所有团队的名称将不同)开头,该字符串由$$M$$(也用空格分隔)字符串中的空格分隔,$$M$$字符串保存有关该团队每个任务状态的信息。

这些字符串的形式为$$SX/V$$,其中:

* $$S$$表示任务的状态—“$$+$$”表示任务已正确解决,“$$-$$”表示任务未正确解决,“$$?$$”意味着上次提交是在排名已经冻结时发送的。
* $$X$$代表该团队为此特定任务发送的提交数量。如果没有为该任务提交任何意见书,则省略该选项。
* $$V$$代表该团队为该特定任务发送最后一次提交的时间。它以$$HH:MM:SS$$(带前导零)的格式给出,并且小于$$5$$小时。如果任务未正确解决(状态“$$-$$”),则省略整个$$/V$$部分。

最后一行是我们的英雄,名为$$NijeZivotJedanACM$$的队伍的未冻结排名。

### 输出格式:

在第一行,也是唯一一行,在排名解冻后,我们的英雄的最差的最终可能位次。

### 得分:
在总共值$$20$$分的测试用例中,输入不包含“$$?$$”
在总共值$$30$$分的测试用例中,对于每个查询都将保证$$(r_{i}-l_{i}≤1000)$$

### 输入样例1:

in
2 1
NijeZivotJedanACM -
ZivotJESTJedanACM -
NijeZivotJedanACM -


### 输出样例1:

out
1


### 输入样例2:

in
3 2
StoJeZivot ?1/04:00:00 +1/02:04:06
JeLiZivotJedanACM ?1/04:59:59 -
NijeZivotJedanACM ?1/04:42:43 -
NijeZivotJedanACM +1/04:42:43 -


### 输出样例2:

out
2

### 输入样例3:

in
7 4
NisamSadaNistaDonio +1/03:59:59 +3/03:42:02 +2/00:14:59 ?1/04:56:12
JeLiMojKockaSeUmio ?4/04:00:00 -3 +1/00:10:01 +9/03:04:42
OstaviDobroJe ?4/04:59:59 -1 +2/00:24:15 +8/03:24:45
DobroJeOstavi +1/01:42:53 - ?9/04:58:23 ?1/04:34:43
NijeZivotJedanACM ?2/04:50:05 ?4/04:32:12 +2/01:32:45 ?1/04:59:59
KoSeToSeta ?1/04:23:32 - +9/01:00:00 -9
SipSipSipSipSipSip - - - ?9/04:00:00
NijeZivotJedanACM -2 +4/04:32:12 +2/01:32:45 +1/04:59:59


### 输出样例3:

out
3


### 第一个例子的说明:
我们的排名解冻后,一切都不会改变。因此,我们的英雄们将永远站在首位!

### 第二个例子的说明:
在最坏的情况下,我们的英雄只会输给斯托杰齐沃特队,从而获得第二名。

### 第三个例子的说明:
在最坏的情况下,我们的英雄将输给纳杰戈雷姆奇和斯卢查朱·纳什特罗贾克·尼萨姆萨丹尼斯塔多尼奥和杰利莫吉科卡苏米奥,从而获得第三名。






答案:若无答案欢迎评论

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。