#P3168. [Heoi2013]钙铁锌硒维生素
[Heoi2013]钙铁锌硒维生素
[HEOI2013] 钙铁锌硒维生素
题目描述
银河队即将参加宇宙比赛,特聘营养师小林负责为选手准备伙食。长途旅行中,选手的营养需求会随时间变化。
小林把需要的营养分为 种,准备两套厨师机器人,每套有 台。每台机器人只能做一道菜,每斤这种菜对各种营养的贡献均已知,单位为微克。机器人可以按输入的数量提供对应份量的菜,也可以生成防止营养摄入过量的药,减少相当于食用相应份量菜所增加的营养。因此,一台机器人对各项营养的净贡献可以按同一个实数倍数缩放,倍数可以为负。
正常工作时,第一套机器人必须能搭配出任意营养需求。第二套机器人用作第一套的备份。请为第一套中的每台机器人任选一台不同的备用机器人。当第一套中的任意一台单独故障时,用分配给它的备用机器人顶替,换完后的 台机器仍要能搭配出任意营养需求。
输入格式
第一行有一个正整数 。
接下来 行,每行 个整数。第 行第 个数表示第一套中第 台机器人做的菜,每斤提供的第 种营养量。
再接下来 行,以相同格式给出第二套机器人的营养量。两套机器人均从 到 编号。
输出格式
无法分配时输出一行 NIE。
可以分配时,第一行输出 TAK。接下来 行,第 行输出第一套第 台机器人的备份编号。如果有多种合法分配,输出备份编号序列字典序最小的一种。
样例
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
数据范围
| 数据比例 | 的限制 |
|---|---|
所有营养量均为 至 之间的整数。
评测说明
保持实数域的线性独立含义,不改为有限域问题。按原题面存档恢复原 20 秒时限,供精确判零使用;本版仍按全部测试点统一评为 100 分。