Cod sursa(job #58361)

Utilizator floringh06Florin Ghesu floringh06 Data 5 mai 2007 18:29:35
Problema Dezastru Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.44 kb

//O(n*k) - dinamic

{$IFDEF NORMAL}
  {$I-,Q-,R-,S-}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
  {$I+,Q+,R+,S-}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
  {$I-,Q-,R-,S-}
{$ENDIF RELEASE}



const nmax=26;
      kmax=26;
      fopen='dezastru.in';
      fclose='dezastru.out';

type matrix = array[0..nmax,0..kmax] of longint;
     vector = array[0..nmax] of extended;


var m:matrix;

    a:array[0..nmax,0..kmax] of extended;

    i,j,k,n:integer;
    fi,fo:text;
    p:vector;
    s:string;

    sol,sum:extended;



   function C(n,k:longint):int64;

     begin

       if n=1 then C:=0
        else if n=k then C:=1
         else if k=1 then C:=n
           else
            if m[n,k]<>0 then C:=m[n,k]
             else
               begin
                m[n,k]:=C(n-1,k)+C(n-1,k-1);
                C:=m[n,k];
               end;

     end;

 procedure write_data;
  begin
  assign(fo,fclose); rewrite(fo);
  writeln(fo,sol:0:6);
  close(fo);
 end;


 procedure solve;
  begin
   sum:=p[1];
   a[1,1]:=p[1];
   for i:=2 to n do
    begin
     sum:=sum+p[i];
     a[i,1]:=sum;
    end;
   for i:=1 to n do
    for j:=2 to k do
      a[i,j]:=a[i-1,j]+a[i-1,j-1]*p[i];
   sol:=a[n,k]/C(n,k);
  end;


 procedure read_data;
  begin
   assign(fi,fopen); reset(fi);
   readln(fi,n,k);
   for i:=1 to n do
       read(fi,p[i]);
   close(fi);
  end;


begin
 read_data;
 solve;
 write_data;
end.