Cod sursa(job #1193223)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 31 mai 2014 12:05:19
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
/*backtracking ... 70p*/

/*using namespace std;
#include <fstream>
#include <iomanip>
ifstream fin("dezastru.in");
ofstream fout("dezastru.out");

int n, k;
int v[30];
float pb=0, prod=1;
float p[30];


void bkt(int) ;

int main()
{
    int i;
    fin>>n>>k;
    for(i=0; i<n; ++i) fin>>p[i];

    for(i=0; i<=n-k; ++i)
    {
        v[0] = i;
        prod = p[i];
        bkt(1);
    }
    for(float fact = k+1; fact<=n; ++fact)
        pb /= fact;
    for(float fact = 1; fact<=n-k; ++fact)
        pb *= fact;
    fout<<fixed<<setprecision(7)<<pb<<'\n';
    return 0;
}


void bkt(int poz)
{   //pozitiile de la 0 la poz-1 sunt ocupate
    if(poz==k) pb += prod;
    else
    {
        for(int i=v[poz-1]+1; i<=poz+n-k; ++i)
        {
            v[poz] = i;
            prod *= p[i];
            bkt(poz+1);
            v[poz] = 0;
            prod /= p[i];
        }
    }
}
*/

/*programare dinamica*/
using namespace std;
#include <fstream>
#include <iomanip>
ifstream fin("dezastru.in");
ofstream fout("dezastru.out");

float p[30];
float prod[27][27];


int main()
{
    int i, j, n, k;
    fin>>n>>k;
    for(i=1; i<=n; ++i) fin>>p[i];

    for(j=1; j<=n; ++j) prod[1][j] = prod[1][j-1]+p[j];
    for(i=2; i<=k; ++i) prod[i][i] = prod[i-1][i-1]*p[j];

    for(i=2; i<=k; ++i)
        for(j=i; j<=n; ++j)
            prod[i][j] = prod[i-1][j-1]*p[j] + prod[i][j-1];

    double pb = prod[k][n];
    for(double fact = k+1; fact<=n; ++fact)
        pb /= fact;
    for(double fact = 1; fact<=n-k; ++fact)
        pb *= fact;
    fout<<fixed<<setprecision(8)<<pb<<'\n';
    return 0;
}