#P17976. Division with Polylines

Division with Polylines

Division with Polylines

题目描述

给定一个 n×nn\times n 的方格,每个格子中有一个数,取值为 −1-1、00 或 11。另外给定四个整数 AL,AD,AR,AUA_L,A_D,A_R,A_U。

请判断能否沿格子的边界画出两条折线:

  • 第一条从方格的左上角到右下角,只能向右或向下走;
  • 第二条从方格的左下角到右上角,只能向右或向上走。

这两条折线将格子划分为左、下、右、上四个区域,各区域允许为空。要求这四个区域中的数之和依次恰好为 AL,AD,AR,AUA_L,A_D,A_R,A_U。

区域的方向与输入顺序有关,不能交换。例如,下面的等价定义明确了交界及空区域的归属:将竖直网格线从左到右编号为 0,1,…,n0,1,\ldots,n。在第 ii 行,记第一条折线向下跨过该行时所在的竖线编号为 pip_i,第二条折线向上跨过该行时的编号为 qiq_i。对于第 jj 列的格子(1≤j≤n1\le j\le n),其归属为:

条件 区域
j≤pij\le p_i 且 j≤qij\le q_i 左
qi<j≤piq_i<j\le p_i 下
j>pij>p_i 且 j>qij>q_i 右
pi<j≤qip_i<j\le q_i 上

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例的第一行包含五个整数 n,AL,AD,AR,AUn,A_L,A_D,A_R,A_U。

接下来 nn 行,每行 nn 个整数,描述方格中的数。保证方格内所有数之和等于 AL+AD+AR+AUA_L+A_D+A_R+A_U。

输出格式

每个测试用例输出一行:若存在符合条件的两条折线,输出 TAK;否则输出 NIE。

数据范围

  • 1≤t≤1000001\le t\le100000,1≤n≤20001\le n\le2000;
  • −n2≤AL,AD,AR,AU≤n2-n^2\le A_L,A_D,A_R,A_U\le n^2;
  • 每个格子中的数均属于 {−1,0,1}\{-1,0,1\};
  • 所有测试用例的 n2n^2 之和不超过 40000004000000。

样例

输入

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

样例说明

前三组使用同一个方格,目标和依次为 (1,0,−2,1)(1,0,-2,1)、(0,2,−3,1)(0,2,-3,1)、(−2,0,1,1)(-2,0,1,1)。前两种可以实现,第三种不能实现。

来源

The 4th Universal Cup, Stage 8: Grand Prix of Poland,原比赛为 AMPPZ 2025。本题面依据官方英文题面重新整理为中文数学描述,保留英文原标题、输入输出、约束与样例。