Cod sursa(job #1817857)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 28 noiembrie 2016 16:14:45
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <iostream>
#include <iomanip>
using namespace std;
ofstream fout ("dezastru.out");
ifstream fin ("dezastru.in");
int i,n,k,v[30],crt,a;
double suma,cost[30],dp[30][30];
void umple()
{
    for( int i = 0 ; i < n ; i++ )
        dp[ i ][ 0 ] = 1;
    for( int i = 1 ; i <= n ; i++ )
        for( int j = 1 ; j <= i ; j++ )
            dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i - 1 ][ j - 1 ] * cost[ i ];
}
int comb( int n , int k )
{
    for( int i = n - k + 1  ; i <= n ; i++ )
        v[ i - n + k ] = i;
    for( int i = 2 ; i <= k ; i++ )
    {
        int put = 2;
        int aux = i;
        while( aux != 1 )
        {
            if( aux % put == 0 )
            {
                while( aux % put == 0)
                {
                    aux /= put;
                    for( int j = 1 ; 1 ; j++ )
                    {
                        if( v[ j ] % put == 0 )
                        {
                            v[ j ] /= put;
                            break;
                        }
                    }
                }
            }
            put++;
        }
    }
    int rsp = 1;
    for( i = n - k + 1 ; i <= n ; i++ )
        rsp *= v[ i - n + k ];
    return rsp;
}
int main()
{
    fin>>n>>k;
    for( i = 1 ; i <= n ; i++ )
        fin>>cost[ i ];
    umple();
    a = comb( n , k );
    setprecision( 8 );
    fout<<fixed<<dp[ n ][ k ] / a;
}