#P3941. Expected Allowance

    ID: 2932 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>动态规划背包Asia Regional ContestAizu2008

Expected Allowance

描述

秀行的父亲氏郷每月会给他一些1000日元的钞票作为零花钱。每月第一天,钞票的数量按以下方式决定:氏郷准备nnmm面骰子,并宣布削减额kk。秀行掷这些骰子,得到的钞票数量是骰子点数之和减去削减额。幸运的是,即使点数之和不超过削减额,氏郷也会承诺至少给他一张钞票。每个骰子的每一面都有从1到mm的点数,且每一面出现的概率相同。

在这个问题中,你需要编写一个程序来计算得到的钞票数量的期望值。

例如,当n=2n=2m=6m=6k=3k=3时,得到1、2、3、4、5、6、7、8和9张钞票的概率分别为136+236+336\frac{1}{36}+\frac{2}{36}+\frac{3}{36}436\frac{4}{36}536\frac{5}{36}636\frac{6}{36}536\frac{5}{36}436\frac{4}{36}336\frac{3}{36}236\frac{2}{36}136\frac{1}{36}

因此,期望值为$\left(\frac{1}{36}+\frac{2}{36}+\frac{3}{36}\right)\times1+\frac{4}{36}\times2+\frac{5}{36}\times3+\frac{6}{36}\times4+\frac{5}{36}\times5+\frac{4}{36}\times6+\frac{3}{36}\times7+\frac{2}{36}\times8+\frac{1}{36}\times9$,约为4.11111111。

输入

输入是一系列行,每行按此顺序包含三个整数nnmmkk。它们满足以下条件:

1n1 \leq n

2m2 \leq m

0k<nm0 \leq k < nm

nm×mn<100000000nm \times mn < 10000000010810^8

输入的结束由一行包含三个零表示。

输出

输出应由一系列行组成,每行包含一个小数。这是得到的钞票数量的期望值,误差可小于10710^{-7}。输出中不应出现其他字符。

输入数据 1

2 6 0
2 6 3
3 10 9
13 3 27
1 2008 3
0 0 0

输出数据 1

7.00000000
4.11111111
7.71000000
1.42902599
1001.50298805