Cod sursa(job #302197)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 8 aprilie 2009 18:58:45
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<math.h>
int n,j,k,ev,as,m,s[30],sol;
float rasp,a[30],t[50001];
    void init()
    {
         s[k]=0;
    }

    int succesor()
    {
        if(s[k]<n)
        {
                  s[k]=s[k]+1;
                  return 1;
        }
        else return 0;
    }

    int valid()
    {
        for(int i=1;i<k;i++)
                if(s[k]==s[i])
                              return 0;
        return 1;
    }

    int solutie()
    {
        if(k==m)
                return 1;
                else return 0;
    }

    void tipar()
    {
         t[sol]=1;
         for(int i=1;i<=m;i++)
                 t[sol]*=a[s[i]];
    }

    void bt()
    {
         k=1;
         init();
         while(k>0)           
         {
                              as=1;ev=0;
                              while(as && !ev)
                              {
                                as=succesor();
                                if(as)ev=valid();
                              }
                              if(as)
                              if(solutie())
                              {
                                           sol++;
                                           tipar();
                              }
                              else
                              {
                                           k++;
                                           init();
                              }
                              else k--;
         }
    }                      

int main()
{
     freopen("dezastru.in","r",stdin);
     freopen("dezastru.out","w",stdout);
     scanf("%d%d",&n,&m);
     for(j=1;j<=n;j++)
                      scanf("%f",&a[j]);
     bt();
     for(j=1;j<=sol;j++)
                      rasp+=(float)t[j]/(float)sol;
     printf("%.6f",rasp);
     return 0;
}