LG#P1068. [NOIP 2009 普及组] 分数线划定

[NOIP 2009 普及组] 分数线划定

P1068 [NOIP 2009 普及组] 分数线划定

题目描述

\hspace{15pt}世博会志愿者的选拔工作正在 A 市如火如荼地进行。为了选拔最合适的人才,A 市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。

\hspace{15pt}面试分数线根据计划录取人数的 150%150\% 划定。即如果计划录取 mm 名志愿者,则面试分数线为排名第 ⌊m×150%⌋\left\lfloor m \times 150\% \right\rfloor 名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

\hspace{15pt}现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

\hspace{15pt}第一行输入两个整数 nn 和 $m \left(5 \leqq n \leqq 5 \times 10^3;\ 3 \leqq m \leqq n\right)$,依次代表报名参加笔试的选手总数和计划录取的志愿者人数。保证 ⌊m×150%⌋≦n\left\lfloor m \times 150\% \right\rfloor \leqq n。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 kik_i 和 $s_i \left(1000 \leqq k_i \leqq 9999;\ 1 \leqq s_i \leqq 100\right)$,依次代表第 ii 名选手的报名号和笔试成绩。保证所有选手的报名号各不相同。

输出格式

\hspace{15pt}第一行输出两个整数,依次代表面试分数线和进入面试的选手的实际人数,相邻两个整数之间用一个空格隔开。

\hspace{15pt}此后每行输出两个整数,依次代表一名进入面试的选手的报名号和笔试成绩,相邻两个整数之间用一个空格隔开。所有选手按照笔试成绩从高到低输出;如果成绩相同,则按报名号由小到大的顺序输出。

测试样例

6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88
88 5
1005 95
2390 95
1000 90
1001 88
3239 88

样例 1 解释

\hspace{15pt}由于 m×150%=3×150%=4.5m \times 150\% = 3 \times 150\% = 4.5,向下取整后为 44。因此面试分数线为排名第 44 的选手的分数,即 8888。由于笔试成绩为 8888 的选手不止一位,所有成绩不低于 8888 的选手都可以进入面试,故最终有 55 个人进入面试。