7227: BZOJ3227：[Sdoi2008]红黑树(tree)

　　红黑树是一类特殊的二叉搜索树，其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-1。 　　一棵红黑树是满足下面“红黑性质”的染色二叉搜索树： 　　(1) 每个结点被染成红色或黑色； 　　(2) 每个前端结点为黑色结点； 　　(3) 任一红结点的子结点均为黑结点； 　　(4) 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。 　　从红黑树中任一结点x出发(不包括结点x)，到达一个前端结点的任意一条路径上的黑结点个数称为结点x的黑高度，记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。 　　给定正整数N，试设计一个算法，计算出在所有含有N个结点的红黑树中，红色内结点个数的最小值和最大值。  

输入格式

　　输入共一个数N。  

输出格式

  　　输出共两行。 　　第一行为红色内结点个数的最小值，第二行为最大值。  

样例输入

8
 

样例输出

1
4
 

提示

对于 100% 的数据，1≤N≤5000

题目来源

没有写明来源