K点游戏

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

/**
 * @Date: 2020-05-02 8:01
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int W = sc.nextInt();
        ArrayList<Integer> ai = new ArrayList<>();//保存结束时的点数
        ArrayList<Double> ai2 = new ArrayList<>();//保存相应点数出现的概率
        getWay(K, W, ai,0,ai2,1);
        double c = 0;
        Iterator<Integer> it = ai.iterator();
        Iterator<Double> it2 = ai2.iterator();
        while (it.hasNext()){
            if (it.next()<=N)
                c+=it2.next();
            else
                it2.next();
        }
        System.out.println(String.format("%.5f",c));
    }

    private static void getWay(int k, int m, ArrayList<Integer> ai,int count,ArrayList<Double> ai2,double num) {
        if (count>=k){
            ai.add(count);
            ai2.add(num);
            return;
        }
        for (int i=1;i<=m;i++){
            getWay(k,m,ai,count+i,ai2,num/m);
        }
    }
}

import java.util.Scanner;

/**
 * @Date: 2020-05-02 9:31
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int W = sc.nextInt();
        System.out.println(String.format("%.5f",new21Game(N,K,W)));
    }
    public static double new21Game(int N, int K, int W) {
        double[] dp = new double[N + W + 1];
        // dp[x] = the answer when Alice has x points
        for (int k = K; k <= N; ++k)
            dp[k] = 1.0;

        double S = Math.min(N - K + 1, W);
        // S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for (int k = K - 1; k >= 0; --k) {
            dp[k] = S / W;
            S += dp[k] - dp[k + W];
        }
        return dp[0];
    }
}