Pagini recente » Borderou de evaluare (job #373669) | Cod sursa (job #1458421) | Cod sursa (job #2427270) | Cod sursa (job #2437304) | Cod sursa (job #1193223)
/*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;
}