[FJOI2017] 树的平均路长问题

题目描述

一棵树 $T$ 的平均路长 $IPL(T)$定义为: $IPL(T)=\sum_{v\varepsilon T}length(path(v))$ 其中, $v$ 是树 $T$ 中的内结点, $length(path(v))$是从树根到结点$v$的路径长度。 红黑树是一类特殊的二叉搜索树,其中每个结点被“染成”红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点,则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为$-1$。除了前端结点外,其他结点均为内结点。 一棵红黑树是满足下面“红黑性质”染色二叉搜索树: 1. 每个结点被染成红色或黑色; 2. 每个前端结点为黑色结点; 3. 任一红结点的儿子结点均为黑结点; 4. 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。 从红黑树中任一结点 $x$ 出发(不包括结点 $x$),到达一个前端结点的任意一条路径上的黑结点个数称为结点 $x$ 的黑高度,记作 $bh(x)$。红黑树的黑高度定义为其根结点的黑高度。 给定正整数 $n$,试设计一个算法,计算出在所有含有 $n$ 个结点的红黑树中,平均路长的最大值。

输入输出格式

输入格式


文件有多个测试项。每行有1个正整数$n$, ($1\le n\le 30000$),表示红黑树的结点数。文件最后以一个$0$结束。

输出格式


对每行中红黑树的结点数 $n$,将计算出的平均路长的最大值输出到文件中。 每行输出一个最大值。 文件最后以一个$0$ 结束。

输入输出样例

输入样例 #1

1
2
3
0

输出样例 #1

1
3
5
0