OI题库

【问题描述】

一个边长为n的正三角形可以被划分成若干个小的边长为1的正三角形，称为单位三角形。

如右图，边长为3的正三角形被分成三层共9个小的正三角形，我们把它们从顶到底，从左到右以1～9编号，见右图。同理，边长为n的正三角形可以划分成n2个单位三角形。

 四个这样的边长为n的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序（从顶向底视角）编号为A, B, C，底面编号为D。侧面的A, B, C号三角形以三棱锥的顶点为顶，底面的D号三角形以它与A，B三角形的交点为顶。左图为三棱锥展开后的平面图，每个面上标有圆点的是该面的顶，该图中侧面A, B, C分别向纸内方向折叠即可还原成三棱锥。我们把这A，B、C、D四个面各自划分成n2个单位三角形。

   对于任意两个单位三角形，如有一条边相邻，则称它们为相邻的单位三角形。显然，每个单位三角形有三个相邻的单位三角形。现在，把1—4n2分别随机填入四个面总共4n2个单位三角形中。

    现在要求你编程求由单位三角形组成的最大排序二叉树。所谓最大排序二叉树，是指在所有由单位三角形组成的排序二叉树中节点最多的一棵树．对于任一单位三角形，可选它三个相邻的单位三角形中任意一个作为父节点，其余两个分别作为左孩子和右孩子。当然，做根节点的单位三角形不需要父节点，而左孩子和右孩于对于二叉树中的任意节点来说并不是都必须的。

【输入】

    输入文件为tree.in。其中第一行是一个整数n(1<=n<=18)，随后的4n2个数，依次为三棱锥四个面上所填的数字。

【输出】

输出文件为tree.out。其中仅包含一个整数，表示最大的排序二又树所含的节点数目。

【样例输入】

3 22 13 9
19 25 15 1
33 20 26 28
32 21 18 7
31 12 17 2
29 24 8 6
3 23 16 36
5 34 27
4 35 11
30 14 10

【样例】

输入文件对应下图：

【样例输出】

17

【提示】

输出样例文件对应的最大排序二叉树如下图所示：