#P50833. 「JOISC 2016 Day 4」最差记者 2
「JOISC 2016 Day 4」最差记者 2
题目描述
题目译自 JOISC 2016 Day4 T3 「最悪の記者 2」
时间来到了 22 世纪,程序设计竞赛已经作为一种智力运动被广泛接受,并且经常出现在各种新闻媒体中,如电视和报纸。
你是 JOI 新闻社的一名记者,负责写报道程序设计竞赛的文章。
昨天举行了一场世界级的程序设计竞赛,共有 名选手参加。为了写一篇关于这个竞赛的文章,你得知了如下信息:
- 作为国际奥林匹克竞赛,选手来自于不同的国家。国家从 到 编号,可能有多于一名选手来自同一国家,也可能有一些国家的选手没有参赛;
- 比赛共 小时;
- 选手在比赛中获得的分数不会在获得之后减少;
- 在比赛开始两小时的时候,不存在两名选手平手。在此时的榜单上,排名第 的选手来自国家 ,并获得了 分;
- 在比赛结束的时候,不存在两名选手平手。在终榜上,排名第 的选手来自国家 ,并获得了 分。
然而,在写文章的阶段,发现榜上显示的选手国家是有问题的。榜上选手的国籍可能显示有误,但是显示的选手分数是一定正确的。
所以,你可以通过修改同一选手的国籍来避免矛盾(但是你不能修改选手的得分)。也就是说,我们要通过修改 中尽可能少的值,使得满足以下条件:
- 存在一个 的排列 ,对于每个 ,满足 且 。
请求出最少要做出多少次修改才能使给出的信息不会互相矛盾。
输入格式
第一行一个整数 ;
接下来 行中的第 行,每行两个整数 ,表示比赛开始两小时后,排名第 的选手来自国家 并获得了 分;
接下来 行中的第 行,每行两个整数 ,表示比赛结束后,排名第 的选手来自国家 并获得了 分。
输出格式
输出一行一个整数,表示要使给出的榜单不互相矛盾的话至少要改多少次。
样例 1
3
3 500
2 200
1 100
1 1000
3 700
3 400
1
这里将 的值修改为 ,就可以使得给出信息不互相矛盾了:
- 比赛开始两小时的时候,来自国家 的选手获得了 分并排名第一,结束时排名第二,获得了 分;
- 比赛开始两小时的时候,来自国家 的选手获得了 分并排名第二,结束时排名第三,获得了 分;
- 比赛开始两小时的时候,来自国家 的选手获得了 分并排名第三,结束时排名第一,获得了 分。
如果将 修改为 ,那么来自国家 的选手在比赛开始两小时时获得了 分,但结束时获得了 分,与规则矛盾。
是可能修改的最少次数,因此输出 。
3
3 3
3 2
1 1
3 4
3 2
1 1
0
这组样例中,即使信息可能有误,但是两份榜单不互相矛盾,所以输出 。注意可以有选手在比赛开始两小时之后成绩没有增加,也可以有多个选手来自同一国家。
6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10
3
将 改为 , 改为 , 改为 ,榜单就不会互相矛盾了。
数据范围与提示
对于全部数据,。输入保证 ,并且保证存在至少一组修改方案使得榜单不会互相矛盾。
详细子任务及附加限制如下表:
子任务编号 | 分值 | |
---|---|---|
无附加限制 |