Problem: Example

Input

1 10 2
1 1 1


Output

2.0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y)     cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << '\n'
#define DDD(x,y,z)  cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << "   " << #z << " = " << z << '\n'
#define DBG         cerr << __LINE__ << ": Hi" << '\n'
#define pb          push_back
#define PI          acos(-1.00)
#define xx          first
#define yy          second
#define eps         1e-9

typedef unsigned long long int ULL;
typedef long long int LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
#define MAX     1000
int k, failCost[MAX+10];

double dp[MAX+10], minCost[MAX+10][40][MAX+10], avg[40];
double solve(int n);
double call(int have, int needToUse, int curLen)
{
    assert(have >= needToUse);
    if(needToUse == 0)
    {
//        DBG;
        return solve(have) + failCost[0];
    }
    int total = have + curLen;
    double p = ((double)(curLen+1))/(total+1); /// probability of this failing
    if(have == needToUse)
    {
//        DBG;
//        D(p*failCost[needToUse]);
        double ret = p * (solve(curLen) + failCost[needToUse]);
        ret += (1-p) * (avg[needToUse]);
        return ret;
    }
//    assert(false);
    double &ret = minCost[have][needToUse][curLen];
    if(ret == ret)
        return ret;



    /// pick this

    double tmp = p * (solve(curLen) + failCost[needToUse])
                +(1-p) * call(have-1, needToUse-1, 0);

    ret = tmp;

    /// dont pick this
    tmp = call(have-1, needToUse, curLen+1);

    ret = min(ret, tmp);
    return ret;
}

double solve(int n)
{
//    D(n);
    if(n == 0)
        return 0;
    double &ret = dp[n];
    if(ret == ret)
        return ret;
    ret = 1e100;
    for(int i = 1; i<=min(n,k); i++)
    {
        ret = min(ret, call(n, i, 0));
    }
    return ret;
}
int main()
{
//    freopen("maxon.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int a, b;
    sfff(a,b,k);
    for(int i = 0; i<=k; i++)
        sf(failCost[i]);
    for(int i = 0; i<=k; i++)
    {
        for(int firstFail = 2; firstFail <= i+1; firstFail++)
        {
            avg[i] += (1.0/(i)) * failCost[i-firstFail+1];
        }
    }
    mem(dp, -1);
    mem(minCost, -1);
    printf("%.9f\n",solve(b-a+-1));
    return 0;
}