测试数据来自 system/1984

描述

一棵含n个叶结点的二叉树可以通过如下方式生成。初始时只有根结点。首先，将根结点展开（本题中的展开是指给一个叶添上左、右两子）；然后，等概率的随机将两个叶结点中的一个展开；之后，每次在当前二叉树的所有叶结点中，等概率地随机选择一个，将其展开。不断地重复这一操作，直至产生n个叶结点为止。

对于按这种方式随机生成的一棵含n个叶节点的二叉树，求（1）叶结点平均深度的数学期望值；（2）树深度的数学期望。约定根结点的深度为0。

格式

输入格式

输入仅有一行，包含两个正整数q和n，分别表示问题编号以及叶结点的个数。

输出格式

输出仅有一行，包含一个实数d，四舍五入精确到小数点后6位。如果q=1，则d表示叶结点平均深度的数学期望值；如果q=2，则d表示树深度的数学期望。

样例1

样例输入1

1 4

样例输出1

2.166667

样例2

样例输入2

2 4

样例输出2

2.666667

样例3

样例输入3

1 12

样例输出3

4.206421

样例4

样例输入4

2 12

样例输出4

5.916614

限制

有\(20\%\)的数据，\(q=1\)，且\(2\le n\le 10\)；
有\(30\%\)的数据，\(q=1\)，且\(2\le n\le 100\)；
有\(20\%\)的数据，\(q=2\)，且\(2\le n\le 10\)；
有\(30\%\)的数据，\(q=2\)，且\(2\le n\le 100\)。

来源

SHTSC 2012 Day1