2014
02-21

# Expected Allowance

Hideyuki is allowed by his father Ujisato some 1000 yen bills every month for his pocket money.In the first day of every month, the number of bills is decided as follows. Ujisato prepares n pieces of m-sided dice and declares the cutback k. Hideyuki rolls these dice. The number of bills given is the sum of the spots of the rolled dice decreased by the cutback. Fortunately to Hideyuki, Ujisato promises him to give at least one bill, even if the sum of the spots does not exceed the cutback. Each of the dice has spots of 1 through m inclusive on each side, and the probability of each side is the same.

In this problem, you are asked to write a program that finds the expected value of the number of given bills.

For example, when n = 2, m = 6 and k = 3, the probabilities of the number of bills being 1,2, 3, 4, 5, 6, 7, 8 and 9 are ,respectively
Therefore, the expected value is
which is approximately 4.11111111..

The input is a sequence of lines each of which contains three integers n, m and k in this order.
They satisfy the following conditions.
1 ≤ n
2 ≤ m
0 ≤ k < nm
nm × m^n < 100000000 (10^8)
The end of the input is indicated by a line containing three zeros.

The input is a sequence of lines each of which contains three integers n, m and k in this order.
They satisfy the following conditions.
1 ≤ n
2 ≤ m
0 ≤ k < nm
nm × m^n < 100000000 (10^8)
The end of the input is indicated by a line containing three zeros.

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

7.00000000
4.11111111
7.71000000
1.42902599
1001.50298805

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int N=100000;
int dp[2][N];
int main()
{
int n,m,k;
while(scanf("%d %d %d",&n,&m,&k)!=EOF)
{
if(n==m&&m==k&&k==0)
break;
memset(dp,false,sizeof(dp));
for(int i=1;i<=m;i++)
dp[1][i]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i*m;j++)
for(int t=1;t<=m;t++)
dp[i&1][j+t]+=dp[(i-1)&1][j];
memset(dp[(i-1)&1],false,sizeof(dp[(i-1)&1]));
}
double ans=0.0;
int i,j;
for(i=1;i<=k+1;i++)
ans+=dp[n&1][i];
j=2;
while(i<=n*m)
{
ans+=dp[n&1][i]*j;
i++;
j++;
}
int tmp=1;
i=1;
while(i<=n)
{
tmp=tmp*m;
i++;
}
printf("%.8lf\n",ans/tmp);
}
return 0;
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧