#P18166. ICPC Inference
ICPC Inference
ICPC Inference
考虑一场有 13 道题的 ICPC 比赛。队伍可以提交程序,结果为正确或错误。
某队第一次正确通过一道题时,通过题数增加 1,总罚时增加该次提交距比赛开始的分钟数,再加上该队此前对这道题的每次错误提交对应的 20 分钟。已经正确通过一道题后,对该题的所有后续提交都被忽略,不影响成绩。
排名首先按通过题数从多到少排序,再按总罚时从少到多排序;仍相同则随机决定先后。
比赛刚结束,共持续 分钟, 支队伍提交了 次程序。有正成绩,也就是至少通过一道题的前三名队伍将登上领奖台。
评委暂时不看提交结果,甚至不知道每次提交对应哪一道题。他们只知道提交时间和提交队伍,想知道领奖台可能是什么样子。
请计算可能出现的有序三队序列数。三队分别是第一、第二、第三名,并且都至少通过一道题。忽略最终只有不到三队通过题目的情况。
输入格式
第一行三个整数 ,均满足 。
接下来 行,第 行两个整数 :
- ,表示提交队伍编号;
- ,表示提交时间;
- 保证 ,提交按时间非降排列,允许同一分钟多次提交。
输出格式
输出一个整数,表示可能的有序前三名队伍序列数。不取模。
样例 1
输入:
4 3 300
1 10
2 25
2 30
3 50
输出:
3
三种可能的领奖台为:
(1,2,3):三队各通过一道题,罚时可以是(10,25,50)、(10,30,50)或(10,50,50)。最后一种情况对应 2 号队第一次提交错误、第二次正确且两次都提交同一道题。(1,3,2):三队罚时为(10,50,50),同分时随机决定 3 号队在 2 号队之前。(2,1,3):2 号队通过两道题,另两队各通过一道题。
样例 2
输入:
4 6 200000
6 1
6 1
1 2
2 2
输出:
4
可能的序列为 (1,2,6)、(2,1,6)、(6,1,2)、(6,2,1)。