#P17848. [ONTAK 2021]ZOD
[ONTAK 2021]ZOD
多米诺骨牌谜题
本题有两个部分。一份输入只包含其中一个部分,由第一行的 指定。
第一部分:多米诺骨牌
给定 ,有 张骨牌,分别标着每个无序数对 ,。每张骨牌的两半必须占据两个共边相邻的整数网格格子,骨牌之间不能重叠。
请摆放全部骨牌,使得对于每个数值 ,所有写着 的格子按上下左右相邻关系连通。可以翻转骨牌。
第二部分:长条铺砖
给定 的矩形棋盘,移除第 行第 列的格子。请用任意数量的 长条覆盖其余全部格子。长条可以横放或竖放,但不得重叠或越界。
输入格式
第一行 ,第二行用例数 。
- 若 ,接下来 行各包含一个 。
- 若 ,接下来 行各包含 ,行列编号从 开始。
输出格式
每个用例无解时输出 NIE;有解时输出 TAK 并给出一种构造。
- 第一部分:按 的顺序输出骨牌。每张骨牌一行四个整数,前两个是较小数所在格子的坐标,后两个是较大数所在格子的坐标。相等时任意顺序。坐标可为负数。
- 第二部分:输出 行,每行 个整数。被移除格子输出 ;其他格子输出覆盖它的长条编号,范围是 。每个使用的编号必须恰好出现在三个共线连续格子中,编号不要求连续。
数据范围
。第一部分 ;第二部分 ,,。
原赛两个部分各占 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 分。