#P3848. ZCC loves ranklist
ZCC loves ranklist
P3848 ZCC loves ranklist(排名表)
题目描述
ZCC 班上的学生家长要求老师 GPS 公布学生的考试排名,但这样可能引起一些问题。于是 GPS 准备只公布前 次考试的排名表,并希望各个学生在这 次考试中的排名之和尽量接近。
班里有 名学生。每次考试都必须给出 这 个不同的排名,同一次考试中没有并列名次。
任务一: 安排前 次考试的排名,使所有学生的排名和中的最大值与最小值之差尽可能小。输出这个最小差值,并给出一种对应的排名安排。
与此同时,为体现学生之间的差异,GPS 为相邻两次考试定义了进步指数。设某名学生上一次考试的排名为 ,本次考试的排名为 ,则
$$P(a,b)=\begin{cases} 0,&a=b,\\ a-b-\dfrac{\max(a,b)}{n},&b>a,\\ a-b+\dfrac{\max(a,b)}{n},&b<a. \end{cases}$$注意,式中的除法为实数除法;排名数字越小表示名次越靠前。
GPS 要求这些进步指数满足:
- 在同一对相邻考试之间,不同学生的进步指数不能相同(按带符号的数值比较)。
- 在不同的相邻考试对之间,任意两个进步指数的绝对值不能相同。
任务二: 判断能否安排恰好 次考试,使上述两项进步指数限制始终成立。如果可以,输出 Yes,否则输出 No。当答案为 Yes 且 时,还必须给出一组具体的 次考试排名安排。若 ,只需输出 Yes 或 No,不需要给出任务二的排名表。
两个任务相互独立。
输入格式
包含多组测试数据,以文件结束(EOF)为终止,测试组数不超过 。
每组数据仅一行,给出两个整数 ,分别表示班级学生人数和任务一中要公布的考试次数。
输出格式
对于第 组数据,先输出一行:
Case #t:
接着输出任务一的结果:
- 第一行是最小的“最大排名和减最小排名和”。
- 接下来 行,每行 个整数,第 行第 个整数表示第 名学生在第 次考试中的排名。
然后输出任务二的结果:
- 一行
Yes或No。 - 若为
Yes且 ,再输出 行,每行 个整数,第 行第 个整数表示第 名学生在第 次考试中的排名。
若合法答案不唯一,可以输出任意一种。本题是构造题,需要 SPJ 判定。
样例输入
3 3
4 2
样例输出
Case #1:
0
1 2 3
2 3 1
3 1 2
No
Case #2:
0
1 4
2 3
3 2
4 1
Yes
1 2 4 1
2 1 3 2
3 4 2 3
4 3 1 4
数据范围
对于每组输入:
$$2\le n\le10000,\qquad1\le k\le n,\qquad nk\le10000.$$测试组数不超过 。任务二仅在 且答案为 Yes 时要求输出具体排名表。