#P3168. [Heoi2013]钙铁锌硒维生素

    ID: 2344 传统题 20000ms 512MiB 尝试: 788 已通过: 209 难度: 9 上传者: 标签>难度分类省选/NOI-线性代数与代数行列式Gauss–Jordan 消元矩阵求逆矩阵乘法秩判定图论二分图建模Kuhn 算法随机化与近似多次独立采样CF2600

[Heoi2013]钙铁锌硒维生素

[HEOI2013] 钙铁锌硒维生素

题目描述

银河队即将参加宇宙比赛,特聘营养师小林负责为选手准备伙食。长途旅行中,选手的营养需求会随时间变化。

小林把需要的营养分为 nn 种,准备两套厨师机器人,每套有 nn 台。每台机器人只能做一道菜,每斤这种菜对各种营养的贡献均已知,单位为微克。机器人可以按输入的数量提供对应份量的菜,也可以生成防止营养摄入过量的药,减少相当于食用相应份量菜所增加的营养。因此,一台机器人对各项营养的净贡献可以按同一个实数倍数缩放,倍数可以为负。

正常工作时,第一套机器人必须能搭配出任意营养需求。第二套机器人用作第一套的备份。请为第一套中的每台机器人任选一台不同的备用机器人。当第一套中的任意一台单独故障时,用分配给它的备用机器人顶替,换完后的 nn 台机器仍要能搭配出任意营养需求。

输入格式

第一行有一个正整数 nn。

接下来 nn 行,每行 nn 个整数。第 ii 行第 jj 个数表示第一套中第 ii 台机器人做的菜,每斤提供的第 jj 种营养量。

再接下来 nn 行,以相同格式给出第二套机器人的营养量。两套机器人均从 11 到 nn 编号。

输出格式

无法分配时输出一行 NIE。

可以分配时,第一行输出 TAK。接下来 nn 行,第 ii 行输出第一套第 ii 台机器人的备份编号。如果有多种合法分配,输出备份编号序列字典序最小的一种。

样例

3
1 0 0
0 1 0
0 0 1
2 3 0
0 7 8
0 0 9
TAK
1
2
3
4
2 0 1 3
0 1 0 4
1 9 9 4
0 4 1 7
1 10 9 8
1 13 10 11
1 2 1 5
2 1 1 7
TAK
3
4
1
2

数据范围

数据比例 nn 的限制
10%10\% n=2n=2
20%20\% n≤10n\le 10
40%40\% n≤30n\le 30
60%60\% n≤50n\le 50
80%80\% n≤100n\le 100
100%100\% 1≤n≤3001\le n\le 300

所有营养量均为 00 至 10 00010\,000 之间的整数。

评测说明

保持实数域的线性独立含义,不改为有限域问题。按原题面存档恢复原 20 秒时限,供精确判零使用;本版仍按全部测试点统一评为 100 分。