logo AlgoBeat OnlineJudge
登录 注册

#102549. [BZOJ 2549] [Ctsc2001]最优据排序二叉树

内存限制:128 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一个边长为 的正三角形可以被划分成若干个小的边长为 的正三角形,称为单位三角形。如下图,边长为 的正三角形被分成三层共 个小的正三角形,我们把它们从顶到底,从左到右以 编号。同理,边长为 的正三角形可以划分成 个单位三角形。

![](./2099/file/pic1.png =100x100)

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

![](./2099/file/pic2.png =100x90)

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

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

输入格式

其中第一行是一个整数 ,随后 行,依次为三棱锥四个面上所填的数字。

输出格式

其中仅包含一个整数,表示最大的排序二叉树所含的节点数目。

样例

样例输入 #1

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

样例输出 #1

17

样例说明 1

数据范围与提示

对于 的数据,