#8633. 「L2-046」天梯赛的赛场安排 普及/提高−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

天梯赛使用 监考系统,需要将参赛队员安排到系统中的虚拟赛场里,并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们,以

便发放比赛账号。为了尽可能减少教练和监考的沟通负担,我们要求赛场的安排满足以下条件:

每位监考老师负责的赛场里,队员人数不得超过赛场规定容量

每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练,且每个赛场的监考老师都不相同。

为此我们设计了多轮次排座算法,按照尚未安排赛场的队员人数从大到小的顺序,每一轮对当前未安排的人数最多的学校进行处理。

记当前待处理的学校未安排人数为

  • 如果 n≥C,则新开一个赛场,将 位队员安排进去。剩下的人继续按人数规模排队,等待下一轮处理;
  • 如果 n<C,则寻找剩余空位数大于等于 的编号最小的赛场,将队员安排进去;
  • 如果 n<C,且找不到任何非空的、剩余空位数大于等于 的赛场了,则新开一个赛场,将队员安排进去。

由于近年来天梯赛的参赛人数快速增长,2023年超过了 所学校 万人,所以我们必须写个程序来处理赛场安排问题。

输入格式

输入第一行给出两个正整数 ,分别为参赛学校数量和每个赛场的规定容量,其中 <

随后 行,每行给出一个学校的缩写(为长度不超过 的非空小写英文字母串)和该校参赛人数(不超过 的正整数),其间以空格分隔。

题目保证每所学校只有一条记录。

输出格式

按照输入的顺序,对每一所参赛高校,在一行中输出学校缩写和该校需要联系的监考人数,其间以 空格分隔。

最后在一行中输出系统中应该开设多少个赛场。

样例

样例输入

10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20

样例输出

zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16