#P17976. Division with Polylines
Division with Polylines
Division with Polylines
题目描述
给定一个 的方格,每个格子中有一个数,取值为 、 或 。另外给定四个整数 。
请判断能否沿格子的边界画出两条折线:
- 第一条从方格的左上角到右下角,只能向右或向下走;
- 第二条从方格的左下角到右上角,只能向右或向上走。
这两条折线将格子划分为左、下、右、上四个区域,各区域允许为空。要求这四个区域中的数之和依次恰好为 。
区域的方向与输入顺序有关,不能交换。例如,下面的等价定义明确了交界及空区域的归属:将竖直网格线从左到右编号为 。在第 行,记第一条折线向下跨过该行时所在的竖线编号为 ,第二条折线向上跨过该行时的编号为 。对于第 列的格子(),其归属为:
| 条件 | 区域 |
|---|---|
| 且 | 左 |
| 下 | |
| 且 | 右 |
| 上 |
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例的第一行包含五个整数 。
接下来 行,每行 个整数,描述方格中的数。保证方格内所有数之和等于 。
输出格式
每个测试用例输出一行:若存在符合条件的两条折线,输出 TAK;否则输出 NIE。
数据范围
- ,;
- ;
- 每个格子中的数均属于 ;
- 所有测试用例的 之和不超过 。
样例
输入
5
5 1 0 -2 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 0 2 -3 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 -2 0 1 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
2 1 -1 0 1
1 0
-1 1
1 0 0 0 0
0
输出
TAK
TAK
NIE
NIE
TAK
样例说明
前三组使用同一个方格,目标和依次为 、、。前两种可以实现,第三种不能实现。
来源
The 4th Universal Cup, Stage 8: Grand Prix of Poland,原比赛为 AMPPZ 2025。本题面依据官方英文题面重新整理为中文数学描述,保留英文原标题、输入输出、约束与样例。