Cod sursa(job #275859)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 10 martie 2009 18:28:44
Problema Dezastru Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include<stdio.h>
#include<math.h>
long totals,n,j,k,ev,as,m,s[100],sol,frecv[1001];
long long fact[26];
float poq,rasp,a[40];
    void init()
    {
         s[k]=0;
    }

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

    int valid()
    {
        if(frecv[s[k]]>1)
                              return 0;
        return 1;
    }

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

    void tipar()
    {
         rasp=rasp+(float)poq/(float)totals;
         poq/=a[s[k]];
    }

    void bt()
    {
         k=1;
         init();
         while(k>0)           
         {
                              as=1;ev=0;
                              while(as && !ev)
                              {
                                as=succesor();
                                if(as)ev=valid();
                              }
                              if(as)
                              {
                                    frecv[s[k]]++;
                                    if(solutie())
                                    {
                                           poq*=(float)a[s[k]];
                                           sol++;
                                           tipar();
                                    }
                                    else
                                    {
                                           if(k<=m)
                                                  poq*=(float)a[s[k]];
                                           k++;
                                           init();
                                    }
                              }
                              else 
                              {
                                   frecv[s[k]]--;
                                   poq/=a[s[k-1]];
                                   k--;
                              }
         }
    }                      

int main()
{
     freopen("dezastru.in","r",stdin);
     freopen("dezastru.out","w",stdout);
     scanf("%ld%ld",&n,&m);
     for(j=1;j<=n;j++)
                      scanf("%f",&a[j]);
     totals=1;
     for(j=n-m+1;j<=n;j++)
                          totals*=j;
     poq=1;
     bt();
     printf("%.6f",rasp);
     return 0;
}