B - Full of 2x2
問題文
はじめに整数 $T$ が与えられます。$T$ 個のテストケースについて次の問題に答えてください。
高さ、幅、奥行きがそれぞれ $A,B,C$ である直方体の箱に、高さ、幅、奥行きがそれぞれ $2, 2, 1$ である直方体のブロックを重ならないように配置するとき、配置することのできるブロックの最大個数とそれを実現する配置方法を出力してください。 ただし、ブロックは回転させることが可能です。
より厳密には、以下の条件をすべて満たすようなブロックの配置方法を出力してください。
- 箱全体を辺の長さがすべて $1$ の単位立方体 $A \times B \times C$ 個で区切ったとき、各ブロックはちょうど $4$ つの単位立方体と重なっている。また、それぞれの単位立方体は、高々 $1$ つのブロックと重なっている。
- 箱の頂点のうち $2$ つが $(0,0,0)$ と $(A,B,C)$ に一致するような $3$ 次元空間において、各ブロックは以下の条件をすべて満たす。
- すべての頂点は格子点に一致する。
- すべての辺は $x$ 軸、$y$ 軸、$z$ 軸のいずれかと平行である。
- すべての頂点について、頂点の座標を $(x,y,z)$ とすると $0\le x \le A$, $0\le y \le B$, $0\le z \le C$ をすべて満たす。
制約
- $1 \leq T \leq 10^{5}$
- $1 \leq A,B,C \leq 10^{6}$
- $1 \leq A \times B \times C \leq 10^{6}$
- 各入力ファイル内の $A \times B \times C$ の総和は $10^{6}$ を超えない
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられます。
$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$
各テストケースは以下の形式で与えられます。
$A$ $B$ $C$
出力
各テストケースについて、答えを次の形式で出力してください。
$A \times B + 1$ 行出力してください。
$1$ 行目には配置することのできるブロックの最大個数 $K$ を出力してください。
続く $A \times B$ 行には以下の形式にしたがってブロックの配置を出力してください。
$\mathrm{plane}_1$
$\mathrm{plane}_2$
$\vdots$
$\mathrm{plane}_{A}$
$\mathrm{plane}_{i}$ は以下の形式で表されます。
$v_{i,1,1}$ $v_{i,1,2}$ $\dots$ $v_{i,1,C}$
$v_{i,2,1}$ $v_{i,2,2}$ $\dots$ $v_{i,2,C}$
$\vdots$
$v_{i,B,1}$ $v_{i,B,2}$ $\dots$ $v_{i,B,C}$
ただし、各 $v_{i,j,k}$ は $2$ つの頂点が $(i-1,j-1,k-1)$ と $(i,j,k)$ に一致する単位立方体に割り当てられた値で、以下の条件をすべて満たす必要があります。
- $0 \leq v_{i,j,k} \leq K$
- 同じブロック内の $4$ つの単位立方体の値は等しい。
- 異なるブロックと重なる単位立方体の値は異なる。
- ブロックと重ならない単位立方体の値は $0$ である。
3
2 3 2
4 5 5
1 1 1
3
1 1
2 2
2 2
1 1
3 3
3 3
24
1 1 2 2 21
5 5 6 6 21
5 5 6 6 22
7 7 8 8 22
7 7 8 8 0
1 1 2 2 21
9 9 10 10 21
9 9 10 10 22
11 11 12 12 22
11 11 12 12 0
3 3 4 4 23
13 13 14 14 23
13 13 14 14 24
15 15 16 16 24
15 15 16 16 0
3 3 4 4 23
17 17 18 18 23
17 17 18 18 24
19 19 20 20 24
19 19 20 20 0
0
0
$1$ 番目のテストケースについて説明します。
1 に対応するブロックは頂点のうち $2$ つが $(0, 0, 0)$ と $(2, 1, 2)$ に一致するように配置されています。また、2 に対応するブロックは頂点のうち $2$ つが $(0, 1, 0)$ と $(1, 3, 2)$ に一致するように配置されています。さらに、3 に対応するブロックは頂点のうち $2$ つが $(1, 1, 0)$ と $(2, 3, 2)$ に一致するように配置されています。ブロックを $4$ 個以上配置することは不可能です。