笃志以砺，决起而飞

本解题报告非本人原创，程序为本人原创。转载请注明出处并保留本注释。 题目描述 Polygons 两个做游戏的人在玩一种多边形游戏。一个有n个顶点的凸多边形需要由 n－3条对角线划分成n－2个三角形。这些对角线只会相交在顶点。划分后的三角形中有一个是黑色的，其余的都是白色。两个选手轮流取，每一个选手每一次要从多边形中切下一个三角形。每个选手只允许沿着一条对角线切下一个三角形。切下黑色三角形的选手获得比赛的胜利。 注意：我们称一个多边形是凸多边形当且仅当任意两个顶点的连线都被包含在多边形的内部。

任务：编写程序， 1、从文本文件gra.in中读入关于凸多边形的描述。 2、判断是否先取的选手有一种必胜的策略。 3、将结果写入文件gra.out。

输入： 输入文件gra.in的第一行包含一个整数n，4 <= n <= 50000，表示多边形的顶点数。顶点按顺时针编号为0至n－1。 以下的n－2行描述该多变形划分成的三角形。第i＋1行（1≤i≤n－2）包含三个非负整数，表示第i个三角形的三个顶点的编号。第一个描述的三角形是黑色的。

输出： 输出文件gra.out包含一个单词： ‘TAK’(在波兰文中表示“是”)，如果先走的选手有必胜策略。 ‘NIE’(在波兰文中表示“否”)，如果先走的选手没有必胜策略。

样例输入： 6 0 1 2 2 4 3 4 2 0 0 5 4

样例输出： TAK

《Polygons》解题报告 一、分析。 为了描述方便，我们用三角形的三个顶点的编号来表示三角形，如下图中的黑色三角形为（1，3，6）。 在 下图中，要切下黑色三角形（1，3，6），就必须切下三角形集合{(0,1,6)},{(1,2,3)},{(3,5,6),(3,4,5)}中的两个。 同样，对于任何一个凸多边形，要切下黑色三角形都必须切下三个三角形集合中的两个。切下一个三角形集合所需的步数是一定的，而与切的顺序无关，所以对于任 何一个三角形集合中我们只需考虑集合中三角形的个数而不必考虑分别是哪几个三角形。 设三个三角形集合的元素个数分别为a，b，c。下面的问题就是如何从状态(a,b,c)判断是否有必胜状态。 先分析必胜状态，首先（0,0,1）一定是必胜状态。若初始状态不是（0，0，n）则状态（0,0,c），c>1，实际是不可能出现的。 证明：(1)、状态（0，0，n）不存在。 (2)、若（0，0，c）n>＝c>＝2不存在，由于（0，0，c－1）只能从（0，0，c）和（0，1，c－1）中得到。 状态（0，0，c）不存在，而从（0，1，c－1）出发可以得到比（0，0，c－1）更优的（0，1，c－2），所以不可能选择（0，0，c－1）。 因此，若状态（0，0，（0，0，c－1）也不存在。 所以（0，0，c）,c>1不存在，则（0，0，c－1）也是不存在的。 ∴ 若初始状态不是（0，0，n），则不可能出现（0，0，c），c>1。因此必胜状态只有一个（0，0，1）。 接 着，分析状态（a，b，c），a≠0,令s＝a+b+c，称s为奇数的状态为奇状态，s为偶数的状态为偶状态。由于每一步只能将a，b，c中的一个数减 [...]