#P16432. pm14910最大优美矩阵

pm14910最大优美矩阵

题目背景

星环研究院正在设计一种多通道校准表。每一行代表一次完整校准,每一列代表一个独立通道。为了避免同一通道重复使用相同参数,同一列中的数必须互不相同;同时,每次校准的参数总和又必须固定。

研究员希望在给定参数范围内安排尽可能多次校准。由于本题使用普通文本比较器判定,不使用特殊评测程序,因此你还需要严格按照题目规定的唯一构造方式输出矩阵。

题目描述

给定三个整数 a,b,ca,b,c,其中 a,ba,b 非负,cc 为正整数。

一个矩阵 XX 被称为一个优美的 (a,b,c)(a,b,c)-矩阵,当且仅当它满足:

  1. 矩阵中的每个元素都是 [a,b][a,b] 内的整数;
  2. 矩阵恰好有 cc 列;
  3. 每一列中的所有元素两两不同;
  4. 每一行的元素和都等于
b+(c−1)a. b+(c-1)a.

不同的优美矩阵可以有不同的行数。你需要构造一个行数尽可能多的优美矩阵。

规定的唯一构造方式

为使本题能够使用普通比较器判定,你必须严格按照下面的规则构造矩阵;即使其他矩阵也满足原始条件,也不会被接受。

令

d=b−a, d=b-a,

最大行数为

r=⌊2dc⌋+1. r=\left\lfloor\frac{2d}{c}\right\rfloor+1.

先构造一个 r×cr\times c 的辅助矩阵 YY,行、列下标均从 00 开始。

  1. 对于所有 0≤j<c−10\le j<c-1:
    • 若 jj 为偶数,则 Yi,j=iY_{i,j}=i;
    • 若 jj 为奇数,则 Yi,j=r−1−iY_{i,j}=r-1-i。
  2. 若 cc 为奇数,则覆盖第 c−2c-2 列。令 cur = r - 2,依次处理 i=0,1,…,r−1i=0,1,\ldots,r-1:
    • 令 Yi,c−2=curY_{i,c-2}=\text{cur};
    • 令 cur = cur - 2;
    • 若 cur < 0,则令 cur = r - 1。
  3. 对每一行 ii,令最后一列为
Yi,c−1=d−∑j=0c−2Yi,j.Y_{i,c-1}=d-\sum_{j=0}^{c-2}Y_{i,j}.

最终输出

Xi,j=a+Yi,j.X_{i,j}=a+Y_{i,j}.

输入格式

输入一行三个整数:

a b c

输出格式

第一行输出最大行数 rr。

接下来输出 rr 行,每行 cc 个整数,表示按照题目规定方式构造出的矩阵 XX。

数据范围

对于所有测试数据:

  • 0≤a≤1060\le a\le 10^6;
  • 0≤b≤1060\le b\le 10^6;
  • 2≤c≤502\le c\le 50;
  • c−1≤b−a≤1000c-1\le b-a\le 1000。

样例 1

输入

1 3 3

输出

2
1 1 3
2 2 1

样例 2

输入

1 3 2

输出

3
1 3
2 2
3 1

样例 3

输入

5 10 3

输出

4
5 7 8
6 5 9
7 8 5
8 6 6

样例 4

输入

10 13 4

输出

2
10 11 10 12
11 10 11 11

样例 5

输入

3 10 5

输出

3
3 5 3 4 7
4 4 4 5 5
5 3 5 3 6