Pagini recente » Cod sursa (job #2708249) | rmi30000 | Cod sursa (job #1348803) | Cod sursa (job #405510) | Cod sursa (job #2659949)
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("dezastru.in");
ofstream fout("dezastru.out");
int n, m;
float sol[26];
int viz[26];
int nr_posibilitati;
float suma = 0;
float numere[26];
float produs_total = 1;
void citire()
{
fin >> n >> m;
for(int i = 0; i < n; i++)
{
fin >> numere[i];
produs_total*=(numere[i]);
}
}
void backtracking1(int k)
{
if(k == m)
{
float produs = 1;
for(int i = 0; i < k; i++)
produs*=sol[i];
suma+=(produs);
nr_posibilitati++;
return;
}
for(int i = 0; i < n; i++)
{
if(viz[i] == 0)
{
if(k == 0 || sol[k - 1] < numere[i])
{
viz[i] = 1;
sol[k] = numere[i];
backtracking1(k+1);
viz[i] = 0;
}
}
}
}
void backtracking2(int k)
{
if(k == n - m)
{
float produs = 1;
for(int i = 0; i < k; i++)
produs*=sol[i];
suma+=(produs_total/produs);
nr_posibilitati++;
return;
}
for(int i = 0; i < n; i++)
{
if(viz[i] == 0)
{
if(k == 0 || sol[k - 1] < numere[i])
{
viz[i] = 1;
sol[k] = numere[i];
backtracking2(k+1);
viz[i] = 0;
}
}
}
}
int main()
{
citire();
if(m <= n/2)
backtracking1(0);
else
backtracking2(0);
fout << fixed << setprecision(6) << float(suma/nr_posibilitati);
return 0;
}