#P17848. [ONTAK 2021]ZOD

[ONTAK 2021]ZOD

多米诺骨牌谜题

本题有两个部分。一份输入只包含其中一个部分,由第一行的 Q∈{1,2}Q\in\{1,2\} 指定。

第一部分:多米诺骨牌

给定 nn,有 n(n+1)/2n(n+1)/2 张骨牌,分别标着每个无序数对 (i,j)(i,j),1≤i≤j≤n1\le i\le j\le n。每张骨牌的两半必须占据两个共边相邻的整数网格格子,骨牌之间不能重叠。

请摆放全部骨牌,使得对于每个数值 ii,所有写着 ii 的格子按上下左右相邻关系连通。可以翻转骨牌。

第二部分:长条铺砖

给定 n×mn\times m 的矩形棋盘,移除第 aa 行第 bb 列的格子。请用任意数量的 1×31\times3 长条覆盖其余全部格子。长条可以横放或竖放,但不得重叠或越界。

输入格式

第一行 QQ,第二行用例数 TT。

  • 若 Q=1Q=1,接下来 TT 行各包含一个 nn。
  • 若 Q=2Q=2,接下来 TT 行各包含 n,m,a,bn,m,a,b,行列编号从 11 开始。

输出格式

每个用例无解时输出 NIE;有解时输出 TAK 并给出一种构造。

  • 第一部分:按 (1,1),(1,2),…,(1,n),(2,2),…,(n,n)(1,1),(1,2),\ldots,(1,n),(2,2),\ldots,(n,n) 的顺序输出骨牌。每张骨牌一行四个整数,前两个是较小数所在格子的坐标,后两个是较大数所在格子的坐标。相等时任意顺序。坐标可为负数。
  • 第二部分:输出 nn 行,每行 mm 个整数。被移除格子输出 00;其他格子输出覆盖它的长条编号,范围是 [1,nm][1,nm]。每个使用的编号必须恰好出现在三个共线连续格子中,编号不要求连续。

数据范围

1≤T≤3001\le T\le300。第一部分 1≤n≤10001\le n\le1000;第二部分 1≤n,m≤1001\le n,m\le100,1≤a≤n1\le a\le n,1≤b≤m1\le b\le m。

原赛两个部分各占 50 分;本包安排两个部分各 10 个独立测试点,每点 5 分。

样例

2
4
3 3 2 2
4 4 1 1
1 7 1 4
1 7 1 5
NIE
TAK
0 5 5 5
1 2 3 4
1 2 3 4
1 2 3 4
TAK
1 1 1 0 2 2 2
NIE

来源

(https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2021/p/zod/)。中文整理与独立加强数据;本包每题 20 个测试点,每点 5 分。