← 返回题目
题库练习 「POI2010」铁路 Railway
← 上一题 下一题 →

A6244 | 「POI2010」铁路 Railway

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

**译自 POI 2010 Stage 1.「[Kolej](https://szkopul.edu.pl/problemset/problem/TJVrS_hRC8W5Q6ZBW6mETAIm/site/?key=statement)」**

一个铁路包含两个侧线 $1$ 和 $2$ ，左边由 $A$ 进入，右边由 $B$ 出去（如下图所示）。

![捕获.JPG](/uploads/acgo/image/407fca040c323831_07e52e269798.jpg)

有 $n$ 个车厢在通道 $A$ 上，编号为 $1$ 到 $n$ ，它们按照 $a_1,a_2,\cdots ,a_n$ 的顺序进入侧线，想要按照 $1,2,\cdots ,n$ 的顺序从通道 $B$ 出去。
他们可以从 $A$ 到 $1$ 或 $2$ ，然后经过一系列转移从 $B$ 出去（不用考虑容量问题）。求是否能够做到，如果可以，请找出一种方案。

输入格式

第一行一个正整数 $n$ 。
第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ 。

输出格式

第一行一个字符串，如果能够做到，输出 ``TAK` ，否则输出 `NIE`` 。
若能做到，第二行 $n$ 个空格隔开的正整数，表示每个车厢进入的侧线编号。
如果有多解，输出任意一种。

输入输出样例

输入 #1
4
1 3 4 2
输出 #1
TAK
1 1 2 1
输入 #2
4
2 3 4 1
输出 #2
NIE
C++ 编辑器
输入
输出