Cod sursa(job #1805130)

Utilizator BogdanIonesqBogdan Ionescu BogdanIonesq Data 13 noiembrie 2016 15:03:00
Problema Dezastru Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <iomanip>

using namespace std;

ifstream in("dezastru.in");
ofstream out("dezastru.out");

int n, k, niv, nrsol=0;
double prob[30], ans[30];
int sol[30];

int valid(int niv)
{
     for (int i=1; i <niv; i++)
     {
          if ( sol[i] == sol[niv]) return false;
     }

     return true;
}

void back(int niv)
{
     if (niv == k+1)
     {
     /*
          for (int i=1; i <= k; i++)
          {
               out << sol[i] << ' ';
          }

     */
          nrsol++;
          ans[nrsol]=1;
          for (int i=1; i <= k ; i++)
          {
                ans[nrsol] = ans[nrsol]*prob[sol[i]];
          }
          //out <<ans[nrsol] <<  '\n';
     }
     else
     {
          if (niv > 1) sol[niv]=sol[niv-1];
          else sol[niv]=0;
          while (sol[niv] < n-k+niv)
          {
               sol[niv]++;
               if ( valid(niv) == true)
               {
                    back(niv+1);
               }
          }
     }
}

int main()
{
     in >> n >> k;
     for(int i=1; i <= n; i++)
     {
          in >> prob[i];
     }

     back(1);

     double probfinal=0;
     for (int i=1; i <= nrsol; i++)
     {
        probfinal= probfinal + ans[i]/nrsol;
     }
     out << setprecision(6);
     out << probfinal;

     return 0;
}