AOJ-1286 : Expected Allowance

Problem B: Expected Allowance

目が 1〜m までのサイコロをn個振った合計値から k だけ引いた数だけ1000円札がもらえる。
合計値が0以下になった場合でも、最低１枚はもらえる。
m,n,kが与えられたときの、期待値を求めよ。

解法は深さ優先探索。深さNまで求めれば、結果的にN個投げた合計値を求められる。nの値を増やしていくか、減らしていくかは好み。最終的には合計値をm^nで割る事で期待値が求まる。

cout << setprecision(8) << fixed;

小数点を８桁程度まで、表示するのにはsetprecision( )を使えばよい。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1286

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>
#include <iomanip>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int N,M,K;

int dfs(int n, int total)
{
	int res=0;
	if(n == 0){
		return ( (total - K) > 0 ) ? total - K : 1;
	}
	else{
		REP( i, 1, M+1 ){
			res += dfs( n-1, total+i );
		}
	}
	return res;
}

int main()
{
	cout << setprecision(8) << fixed;

	while(cin >> N >> M >> K && N)
	{
		double d = pow(M,N);
		cout << dfs(N,0) / d << endl;
	}

	return 0;
}