本次SGOI的题目大多是数据结构、搜索、图论的经典题目，也是讨论的热点问题，应努力采用较优的算法解决。

教授的测试
(tree.pas/exe)

题意描述：

　　转眼之间，新学期已经过去几个月了，F大学计算机系的W教授决定对他的学生进行一次测试。为了测试学生对树结构的认识，同时也检验他们的编程能力，教授把测试的内容定为：要求学生们编程按编号顺序打印出节点个数不少于m的所有二叉树。

　　二叉树编号规则如下：
　　仅有一个元素的树编号为1。
　　当满足以下条件之一时，定义二叉树a的编号比b大：
　　　　1． a的节点数比b多。
　　　　2． 若a的节点数与b相等，且a的左子树编号比b的左子树大。
　　　　3． a的节点数和左子树编号都和b相等，且a的右子树编号比b的右子树大。

　　二叉树的元素用大写X表示。
　　例如：
　　　

　　打印二叉树的格式为：

　　（ 左子树 ）{若左子树为空，则省略} X{根} （ 右子树 ）{若右子树为空，则省略}

　　例如在上图中，编号为2 的树可表示为：X（X）；
　　　　　　　　　编号为3 的树可表示为：（X）X；
　　　　　　　　　编号为5 的树可表示为：X（（X）X）；

　　当然当m较大时，检验答案对错的工作也是很繁重的，所以教授只打算对其中的若干个编号的二叉树进行抽查，他想麻烦你在测试开始前把标准答案先准备好（教授的测试卷会事先交给你）。

输入：

　　输入文件为教授的测试卷，至少1行，至多10行，每行一个数N（1<=N<=10^8）,即要抽查的二叉树的编号，以零结束。

输出：

　　输出文件是你求出的标准答案，对每一个编号输出其对应的二叉树，每个二叉树占一行，零不用输出。

样例输入（tree.in）：

2
5
0

样例输出（tree.out）：

X（X）
X（（X）X）

 

恺撒的规划
(squares.pas/exe)

问题描述:

　　亚特兰蒂斯是一块富饶美丽的土地。恺撒大帝率领他的大军，经过了一整年的浴血奋战，终于将它纳入了罗马帝国的版图。然而，长期的战火彻底抹去了这里的繁华，昔日的富庶之地如今一片荒芜。恺撒大帝作为一位有着雄才大略的君主，决心在战争的废墟上建起一座更为宏伟的城市。所以，在建城之前，他需要对整个城市进行规划。

　　亚特兰蒂斯是一块矩形平原，恺撒准备在上面修建一些建筑。为了规划方便，他将矩形划分成N*M格。棘手的是，部分古老的神庙残存下来，散布在某些格子内。亚特兰蒂斯的原住民原本就十分信奉神灵，而这些经过战火洗礼的神庙更是被他们视为圣物，是万万不能拆除的，否则将激起民愤，甚至引发暴动。恺撒深知这一点，因此，他的新建筑在选址时要避开这些神庙。

　　假设新的建筑物有P种规格，每种建筑物都是正方形的，占地为TiTi格 (1<=i<=P)。恺撒想知道对于每种规格的建筑，有多少种不同的合适选址方案（一种合适的选址方案指的是在该建筑所占的正方形区域内不存在神庙）。作为他的内务部长，这个光荣而艰巨的任务自然交给你来完成。

输入：

　　输入文件第一行包含三个数，分别代表N,M,P (1<=N,M<=2000,1<=P<=1000)。随后的n行，每行有m个0或1（0表示该格为废墟，1表示该格有神庙）。接下来的P行每行有一个整数 (1<<=max(M,N))，代表的第i种建筑物的边长。

输出：

　　输出文件有P行，每行一个整数，第行的数代表边长为的建筑物选址方案数。

样例输入（squares.in）：

4 4 2
1011
1111
1110
1110
2
3

样例输出(squares.out)：

5
1

 

烦恼的设计师
(flowers.pas/exe)

题意描述:

　　春天到了，百花齐放，西湖公园里新设置了许多花坛，设计师想用不同的花摆出不同的图案以吸引游人，于是设计了各种图案并且在花圃中选好了要摆放的花。不幸的是负责搬运和摆放的工人因为临时有事，只将花放到花架上就匆匆离开了，并没有按照设计师原来的设计方案摆放，结果花坛杂乱不堪,设计师只好自己来调整花的位置。由于设计师通常从事脑力劳动，较少从事搬运和摆放花盆的体力工作，所以请你帮忙找出一种移动方法使工作量最小。

　　不同种类的花有不同的类型编号，虽然地球上花的种类很多，但因为公园里的花不超过1,000,000种，所以花的类型编号不超过1,000,000。另一方面，出于美学考虑，一个花坛里摆放的不同种类的花不超过3种，且不同种类的花的数量不可太接近，对于任意两种花，数量多的花的盆数至少是数量少的花的2倍。

　　花坛是正六边形的，共摆放有19盆花，每盆花都放在一个转盘上，转动一盆花下面的转盘，会使周围的6盆花顺时针或逆时针移动一个位置（但不可把花转到花坛外），称为一次操作。你的任务：用最少的操作使花坛由初始状态转化为符合设计图纸的目标状态。

例如：
　　
　　　　　　　　　初始状态　　　　　　　　　　　　　　目标状态

　　如图，只需将处于圆心位置的那盆花的转盘顺时针转动一个位置，红色的花就移动到了目标位置。

输入：

　　输入文件共11行，１－5行描述花坛的初始状态，7－11行表示花盆应摆放的位置。中间以空行分隔。5行数字分别表示花坛的5个行，其中第1、5两行有3个整数，第2、4两行有4个整数，第3行有5个整数，表示每一行的花的类型，不同的数代表不同种类的花。

输出：

　　输出文件第一行包含一个整数T即最少的操作数，数据保证20步之内有解。以下T行输出操作序列，每行代表一次操作，包括3个整数,,,（,）表示第i步转动第行，第盆花下的转盘，当为0时表示向顺时针方向转动，为1时表示向逆时针方向转动，如有多种方案，任意输出其中一种即可。

样例输入（flowers.in）:

样例输出（flowers.out）：

1
3 2 0

 

采集标本
(gather.pas/exe)

题意描述：

　　3008年3月30日凌晨5：31，联合国星际观测站观测到宇宙深处一次大规模的爆炸，爆炸之后产生了一个新的星系，科学家们发现新星系中的行星十分特殊，这些行星之间存在一些神秘的通道，我们姑且称它们为星际轨道。通过观测发现，这些星际轨道可实现定向的传送且无需耗费额外的能量，换句话说，从某个行星可以通过星际轨道"免费"到达其他某些行星，当然也可能无法到达其他行星（如果没有任何一条星际轨道与该行星相连的话）。也许是因为宇宙黑洞的关系，科学家们发现一个有趣的现象，即不存在两个星球i,j,既能从i到达j，又能从j到达i！

　　这些行星的特殊性带来了巨大的研究价值，所以科学家希望派飞船到行星上采集标本，他们希望能从这些标本中发现一些产生上述奇怪现象的原因，这对于人类研究太空是很重要的。为了节约时间，尽快完成采集工作，科学家希望每个行星都被访问过且仅被访问过一次。由于飞船所能携带的燃料有限，所以飞船在这些行星间的旅行必须通过星际轨道完成。另外，飞船可以从地球发射到任意一个行星上，当它们完成任务后也可以直接回到地球，但是由于该星系与地球之间的距离十分遥远，飞行需要耗费大量的能量，所以科学家们希望派遣最少的飞船去完成任务。于是，日理万机的科学家找到了你，希望你能帮助他们。

输入：

　　输入文件的第一行给定N，M。（N<=200为行星的数量，M<=40000为星际轨道的数量）
　　接下来的M行，每行两个正整数X，Y（X，Y<=N），分别为第M条轨道的起点和终点。

输出：

　　仅一个整数，表示最少需要的飞船数量。

样例输入（gather.in）：

　　5 4
　　1 2
　　2 3
　　1 4
　　3 5

样例输出（gather.out）：

　　2
　（说明：
　　第一艘飞船发射到星球1，通过轨道从星球1星球2，再从星球2星球3，然后返回；
　　第二艘飞船发射到星球4，通过轨道从星球4星球5，然后返回）

 

Darting-Robot
(dart.pas/exe)

题意描述：

　　Newton大学机械系的学生们正在进行一项研究，他们的目标是一台会投飞镖的机器人（他们把它叫做Darting-Robot IV）。之所以叫做"IV"是因为前三次都失败了，他们趴在桌子上仔细研究了一天，结论是以前的控制芯片不过关。经过数次改进，他们觉得机器人的机械部分已经十分完善，现在急需的是一块合格的控制芯片。他们想得到你的帮助。

　　已知镖靶是一个有n个顶点的多边形，被放置在三维坐标系中x轴和z轴所在的平面内。它有一个靶心，为处理方便，靶心与坐标原点重合。将靶心与n个顶点连接，就构成了n个三角形，每个三角形区域都具有一定的分值，如图：
　　

　　而机器人将被放置在3米以外，发射点固定于（0，3，0），机器人每发射一镖都由3个参数：x，y，z。(x，y，z)表示初速度向量方向上的一点。由于技术上的限制，初速度是固定的，都是。（射出的飞镖需要考虑重力加速度的影响。重力加速度）

　　现在，这块控制芯片的要实现的功能是：读取镖靶的信息以及目标分值，计算出达到这个分值所需的最少镖数，以及每一支镖的三个相关参数，你只需求初一组满足条件的解。

　　限制：很明显，不同的飞镖必须扎在不同的位置，另外，飞镖不能扎在不同区域的边界上，这会给裁判增加判罚的难度，他在无奈之下，也许会随便给一个分数。

输入：
　　输入文件的第一行包含一个正整数 n (n<=100)。
　　以下n行每行有两个实数（，），逆时针给出了多边形n个点的坐标。
　　接下来n行每行包括一个整数，对应每个区域的分值。其中，对应（，），（，），（0，0）构成的三角形的分值，以此类推。对应（，），（，），（0，0）构成的三角形的分值。
　　最后一行包括一个整数score，表示目标分数。（score<=10000）
　　输入文件保证有解。

输出：

　　输出文件的第一行包括一个整数m，表示最少镖数。
　　以下每一行每行包括三个实数x，y，z，表示每一镖的参数。（为了保证精度，每个实数都直接输出，不需四舍五入。测试程序可以接受较小的误差）

样例输入（dart . in）：

　　4
　　-1 1
　　-1 -1
　　1 -1
　　1 1
　　1
　　2
　　4
　　8
　　15

样例输出（dart . out）：