Cod sursa(job #1756172)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 12 septembrie 2016 00:58:35
Problema Dezastru Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <cstdio>
#define NMAX 26
using namespace std;

int N,K;

float dp[2][NMAX],v[NMAX];
int pascal[NMAX];

void citire()
{
    scanf("%d%d",&N,&K);
    for(int i=1; i<=N; i++)
        scanf("%ff",&v[i]);
}

void init_dp()
{
    dp[0][1]=v[1];
    for(int i=1; i<=N; i++)
        dp[0][i]=v[i]+dp[0][i-1];
}

void init_pascal()
{
    pascal[0]=1;
    for(int n=1; n<=N; n++)
        for(int k=N; k>=0; k--)
            pascal[k]= pascal[k-1] + pascal[k];
}

void rezolvare()
{
    int x = 1;
    for(int k=2; k<=K; k++)
    {
        for(int i=k; i<=N; i++)
        {
            dp[x][i] = dp[x][i-1] + dp[x^1][i-1] * v[i];

        }
        x = x^1;
    }
    float rez  = dp[K-1][N]/pascal[K];
    printf("%lf",rez);
}


int main()
{
    freopen("dezastru.in","r",stdin);
    freopen("dezastru.out","w",stdout);
    citire();
    init_pascal();
    init_dp();
    rezolvare();

    return 0;
}