#P3848. ZCC loves ranklist

    ID: 3052 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-排列构造分块构造奇偶性分析一般图匹配直接模拟By镇海中学

ZCC loves ranklist

P3848 ZCC loves ranklist(排名表)

题目描述

ZCC 班上的学生家长要求老师 GPS 公布学生的考试排名,但这样可能引起一些问题。于是 GPS 准备只公布前 kk 次考试的排名表,并希望各个学生在这 kk 次考试中的排名之和尽量接近。

班里有 nn 名学生。每次考试都必须给出 1,2,…,n1,2,\ldots,n 这 nn 个不同的排名,同一次考试中没有并列名次。

任务一: 安排前 kk 次考试的排名,使所有学生的排名和中的最大值与最小值之差尽可能小。输出这个最小差值,并给出一种对应的排名安排。

与此同时,为体现学生之间的差异,GPS 为相邻两次考试定义了进步指数。设某名学生上一次考试的排名为 a=OldRanka=\mathrm{OldRank},本次考试的排名为 b=NewRankb=\mathrm{NewRank},则

$$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 要求这些进步指数满足:

  • 在同一对相邻考试之间,不同学生的进步指数不能相同(按带符号的数值比较)。
  • 在不同的相邻考试对之间,任意两个进步指数的绝对值不能相同。

任务二: 判断能否安排恰好 nn 次考试,使上述两项进步指数限制始终成立。如果可以,输出 Yes,否则输出 No。当答案为 Yes 且 n≤100n\le100 时,还必须给出一组具体的 nn 次考试排名安排。若 n>100n>100,只需输出 Yes 或 No,不需要给出任务二的排名表。

两个任务相互独立。

输入格式

包含多组测试数据,以文件结束(EOF)为终止,测试组数不超过 1010。

每组数据仅一行,给出两个整数 n,kn,k,分别表示班级学生人数和任务一中要公布的考试次数。

输出格式

对于第 tt 组数据,先输出一行:

Case #t:

接着输出任务一的结果:

  • 第一行是最小的“最大排名和减最小排名和”。
  • 接下来 nn 行,每行 kk 个整数,第 ii 行第 jj 个整数表示第 ii 名学生在第 jj 次考试中的排名。

然后输出任务二的结果:

  • 一行 Yes 或 No。
  • 若为 Yes 且 n≤100n\le100,再输出 nn 行,每行 nn 个整数,第 ii 行第 jj 个整数表示第 ii 名学生在第 jj 次考试中的排名。

若合法答案不唯一,可以输出任意一种。本题是构造题,需要 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.$$

测试组数不超过 1010。任务二仅在 n≤100n\le100 且答案为 Yes 时要求输出具体排名表。